JPS5897742A - 検索装置 - Google Patents
検索装置Info
- Publication number
- JPS5897742A JPS5897742A JP56195535A JP19553581A JPS5897742A JP S5897742 A JPS5897742 A JP S5897742A JP 56195535 A JP56195535 A JP 56195535A JP 19553581 A JP19553581 A JP 19553581A JP S5897742 A JPS5897742 A JP S5897742A
- Authority
- JP
- Japan
- Prior art keywords
- key
- search
- retrieving
- data
- host computer
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9027—Trees
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
本発明は、情報検索装置、特にＢ −ｔｒｅｅを用いた
データ管理手法を実現する検索装置に関するものである
。
データ管理手法を実現する検索装置に関するものである
。
情報処理装置において、対象となるデータの大容量化お
よびデータの内容による自由な検索など高速処理の必要
性によってデータ管理の要求が高まっている。この中で
Ｂ −ｔｒｅｅ （Ｂｉｎａｒｙ ｔｒｅｅ ）はデー
タ管理の有用な手法であり、データの索引編成として広
く採用されており、データベース管理システムに於いて
も、転置ファイルなど高速検索を前提として、Ｂ−１ｒ
・・およびその修正された手法が多く用いられている＠ ここで、Ｂ−ｔｒｅｅとは、各ＷＩ（ｉｓ＠ｄ＠）にｋ
ｌｌｌｐ分麩ポイ分身ポインタ／）個のキーが格納され
て、ｋの上限をｍとすればｋの最小値がｍ／ａとなるよ
うな木（ｔｒｅｅ ）構造である。ただしＩＩ （ｌ＠
ａｆ ）の節での分岐ポインタは空であり、根幹節（ｔ
ｏ・ｔ）の最小分岐数はコである。このようなり−１ｒ
・・をｍ次のＢ−ｔｒ・・と呼ぶ。
よびデータの内容による自由な検索など高速処理の必要
性によってデータ管理の要求が高まっている。この中で
Ｂ −ｔｒｅｅ （Ｂｉｎａｒｙ ｔｒｅｅ ）はデー
タ管理の有用な手法であり、データの索引編成として広
く採用されており、データベース管理システムに於いて
も、転置ファイルなど高速検索を前提として、Ｂ−１ｒ
・・およびその修正された手法が多く用いられている＠ ここで、Ｂ−ｔｒｅｅとは、各ＷＩ（ｉｓ＠ｄ＠）にｋ
ｌｌｌｐ分麩ポイ分身ポインタ／）個のキーが格納され
て、ｋの上限をｍとすればｋの最小値がｍ／ａとなるよ
うな木（ｔｒｅｅ ）構造である。ただしＩＩ （ｌ＠
ａｆ ）の節での分岐ポインタは空であり、根幹節（ｔ
ｏ・ｔ）の最小分岐数はコである。このようなり−１ｒ
・・をｍ次のＢ−ｔｒ・・と呼ぶ。
ｌｉｔ図に亭次のＢ−ｔｒ・・の例を示すが、ここで、
節／内の数字はキー値を示し、キーの両側には分岐ポイ
ンターが格納されている。各節ｌの構成は全て同じであ
り、キーはキー値の昇順に並べられている。分岐ポイン
タコの指す節ｌには、その分岐ポインタコの左側のキー
より大きく、右側のキーより小さいキーが格納されてい
るが、葉に於ルλては分岐ポインターは空である。さら
に、Ｂ−ｔｒ・・は根幹節から葉に至るレベルが同一で
あるように保持される。このような構成により、ある特
定のキーへ到達する最悪アクセス回数をレベル数とし、
格納域の使用効率を１以上に保証している。Ｂ−ｔｒ・
・の基本的操作はキーの検索、追加、削除であるが、そ
のために必ず上述の構造を保持するように操作される。
節／内の数字はキー値を示し、キーの両側には分岐ポイ
ンターが格納されている。各節ｌの構成は全て同じであ
り、キーはキー値の昇順に並べられている。分岐ポイン
タコの指す節ｌには、その分岐ポインタコの左側のキー
より大きく、右側のキーより小さいキーが格納されてい
るが、葉に於ルλては分岐ポインターは空である。さら
に、Ｂ−ｔｒ・・は根幹節から葉に至るレベルが同一で
あるように保持される。このような構成により、ある特
定のキーへ到達する最悪アクセス回数をレベル数とし、
格納域の使用効率を１以上に保証している。Ｂ−ｔｒ・
・の基本的操作はキーの検索、追加、削除であるが、そ
のために必ず上述の構造を保持するように操作される。
このような情報検索によりデータ管理を行う情報処理装
置においては、主記憶装置の他にＢ−ｔｒ・・の各節を
記憶した補助記憶装置を有し、Ｂ−ｔｒ＠ｅの基本操作
を実現する場合、一般的に補助記憶装置はデータの読み
出し、書込み機能を有し、中央処理装置はＢ−ｔｒｖｅ
の各節を補助記憶装置から主記憶装置へ読出して操作し
、必要に応じて補助記憶装置へ書込む。しかしながら、
従来のこのような方式では、データ検索性能、情報処理
装置の中央処理装置の演算速度、主記憶装置のサイズ及
び主記憶装置と補助記憶装置間のデータ転送速度に依存
しデータ管理に要求される機能が高まるにつれ、上述の
資源の制約から充分な性能が得られないことが多くなっ
ている。また、データ管理による中央処理装置、主記憶
装置の専有率が高まり、情報処理装置全体としてのスル
ープット、レスポンスタイム等が不充分となることも多
い。
置においては、主記憶装置の他にＢ−ｔｒ・・の各節を
記憶した補助記憶装置を有し、Ｂ−ｔｒ＠ｅの基本操作
を実現する場合、一般的に補助記憶装置はデータの読み
出し、書込み機能を有し、中央処理装置はＢ−ｔｒｖｅ
の各節を補助記憶装置から主記憶装置へ読出して操作し
、必要に応じて補助記憶装置へ書込む。しかしながら、
従来のこのような方式では、データ検索性能、情報処理
装置の中央処理装置の演算速度、主記憶装置のサイズ及
び主記憶装置と補助記憶装置間のデータ転送速度に依存
しデータ管理に要求される機能が高まるにつれ、上述の
資源の制約から充分な性能が得られないことが多くなっ
ている。また、データ管理による中央処理装置、主記憶
装置の専有率が高まり、情報処理装置全体としてのスル
ープット、レスポンスタイム等が不充分となることも多
い。
本発明の目的は、このような従来の欠点を除去し、補助
記憶装置がＢ−ｔｒｙ・の検索を行い、検索結果をホス
ト計算機に転送し得る検−索装置を提供することにある
。
記憶装置がＢ−ｔｒｙ・の検索を行い、検索結果をホス
ト計算機に転送し得る検−索装置を提供することにある
。
以下に、図面を参照して本発明の詳細な説明するＯ
第１図は本発明検索装置の構成の一例を示し、ここで、
／／はホスト計算機であり、主記憶装置１２と中央処理
装置１３とを有し、このホスト計算機／／にはデータバ
ス／＃を介して補助記憶装置／ｊを接続する。第３図に
は、この補助記憶装置／ｊの内部構成を示し、Ｉは制御
部、ｎは記憶部である。
／／はホスト計算機であり、主記憶装置１２と中央処理
装置１３とを有し、このホスト計算機／／にはデータバ
ス／＃を介して補助記憶装置／ｊを接続する。第３図に
は、この補助記憶装置／ｊの内部構成を示し、Ｉは制御
部、ｎは記憶部である。
さらに制御部Ｉは、第１図に示すように構成し、ここで
、Ｊ／はホスト計算＠／／から送られてくる検索すべき
キーが格納されるレジスタであり、ホスト計算機／／か
らの検索命令により、その検索キーを比較器３２に供給
する。この比較＠３２には記憶部〃に格納しであるＢ−
ｔｒ・・の節データをも供給する。
、Ｊ／はホスト計算＠／／から送られてくる検索すべき
キーが格納されるレジスタであり、ホスト計算機／／か
らの検索命令により、その検索キーを比較器３２に供給
する。この比較＠３２には記憶部〃に格納しであるＢ−
ｔｒ・・の節データをも供給する。
比較器Ｊ２はクロックφλに従ってλつのデータのキー
値を比較する。３３．評は比較結果をラッチするための
７リツプ７田ツブであり、第３図示のタイミングＴ／で
動作する。フリップ７０ツブ３３は比較結果が等しけれ
ばオン状態となり、７リツプ７０ツブ３ダはＢ−ｔｒｅ
・の節データ中のキー値が大きい場合にオン状態となる
。Ｂは、クロックφｌに従って比較される節データのキ
ーの前の分岐ｌインタを保持するためのレジスタであり
、３６は同じくクロックー−に従って比較される節デー
タのキーの後の分岐ポインタを保持するためのレジスタ
である。
値を比較する。３３．評は比較結果をラッチするための
７リツプ７田ツブであり、第３図示のタイミングＴ／で
動作する。フリップ７０ツブ３３は比較結果が等しけれ
ばオン状態となり、７リツプ７０ツブ３ダはＢ−ｔｒｅ
・の節データ中のキー値が大きい場合にオン状態となる
。Ｂは、クロックφｌに従って比較される節データのキ
ーの前の分岐ｌインタを保持するためのレジスタであり
、３６は同じくクロックー−に従って比較される節デー
タのキーの後の分岐ポインタを保持するためのレジスタ
である。
なお、クロックφ／は節データＶの分岐ポインタｊｌ−
／ 、 ｊ／−λ、・・・に同期して動作する。またタ
イミングＴ／は比較データの終了に同期する。
／ 、 ｊ／−λ、・・・に同期して動作する。またタ
イミングＴ／は比較データの終了に同期する。
次に、本発明検索装置において、検索を行う際の処理の
流れを第１図に従って説明する。まずホスト計算機ｌｌ
から槽動記憶装置／ｊに検索キーと検索命令が順次に転
送されると制御部Ｊのレジスタ３１にこの検索キーが格
納され、続いて記憶部ｎから最初の根幹節データが読み
出されて制御部Ｊに供給され、データ検索が開始される
（手順Ｔ／、Ｔコ。
流れを第１図に従って説明する。まずホスト計算機ｌｌ
から槽動記憶装置／ｊに検索キーと検索命令が順次に転
送されると制御部Ｊのレジスタ３１にこの検索キーが格
納され、続いて記憶部ｎから最初の根幹節データが読み
出されて制御部Ｊに供給され、データ検索が開始される
（手順Ｔ／、Ｔコ。
ＴＪ′）、いま、第７図示のような朧次の根幹節データ
りＯが供給されたとすると、分岐メインタフ１−７に同
期してクロックφｌが動作して、レジスタ３≦にこの分
岐ポインタ７／−ｌがラッチされる（手順Ｔ参）０分岐
ポインタ７／−／に続いて入来したキー’１２−／は比
較器ｎに供給される。比較器ｎでは、このキー７４−／
の入来に同期して動作するクロックφコによりレジスタ
３／から供給された検索キーと、この入来したキー７２
−／との比較を行なう（手順Ｔｊ ’）。
りＯが供給されたとすると、分岐メインタフ１−７に同
期してクロックφｌが動作して、レジスタ３≦にこの分
岐ポインタ７／−ｌがラッチされる（手順Ｔ参）０分岐
ポインタ７／−／に続いて入来したキー’１２−／は比
較器ｎに供給される。比較器ｎでは、このキー７４−／
の入来に同期して動作するクロックφコによりレジスタ
３／から供給された検索キーと、この入来したキー７２
−／との比較を行なう（手順Ｔｊ ’）。
比較結果が等しければ７９ツブ、フシツブｎがオンにな
り（手順Ｔ７）、これによってＩｌ当キーが検出された
ので検索を終了する。しかるに、入来した節データのキ
ー７Ｊ −／が大ならば７リツプ７ｐツブｙがオン状態
になる （手順Ｔｒ）。
り（手順Ｔ７）、これによってＩｌ当キーが検出された
ので検索を終了する。しかるに、入来した節データのキ
ー７Ｊ −／が大ならば７リツプ７ｐツブｙがオン状態
になる （手順Ｔｒ）。
ここで、比較器３２における比較の終了と同期して次の
分岐ポインタ７／−一が入来して、レジスタ３６に格納
される。これにより、レジスタム内に格納されていた分
岐ポインタ７／−／はレジスタＢにシフトされて格納さ
れる（手順〒９）。このレジスタｎに格納された分岐ポ
インタ７／−ｌを取り出し（手１１Ｔ１０）、空である
か否かを判定する（手順Ｔ／／）。
分岐ポインタ７／−一が入来して、レジスタ３６に格納
される。これにより、レジスタム内に格納されていた分
岐ポインタ７／−／はレジスタＢにシフトされて格納さ
れる（手順〒９）。このレジスタｎに格納された分岐ポ
インタ７／−ｌを取り出し（手１１Ｔ１０）、空である
か否かを判定する（手順Ｔ／／）。
空であるならば、検索が葉の節データに達したことが検
知されて、「ＹＫｓＪの流れに沿って進み検索を終了す
る。しかるに、空でない場合には、この分岐ポインタ７
／−／によって指示される記憶部ｎ内の節データを読み
出して制御部Ｉに供給しく手順Ｔｌコ）、再び手順Ｔ、
ｇに戻り、前述した検索動作を繰返す。
知されて、「ＹＫｓＪの流れに沿って進み検索を終了す
る。しかるに、空でない場合には、この分岐ポインタ７
／−／によって指示される記憶部ｎ内の節データを読み
出して制御部Ｉに供給しく手順Ｔｌコ）、再び手順Ｔ、
ｇに戻り、前述した検索動作を繰返す。
一方、手順Ｔ≦においてキー７コーｌが小ならばフリッ
プ７０ツブｎ 、 ７１’がいずれもオフ状態にあり（
手順’ｆ／３ ） 、レジスタ３乙に保持された分岐ポ
インタ７１−２を取り出して、前述したようにして次の
節データの検索に移る。このような動作が該当キーが検
出されるか葉に到達するまで繰返されてＢ−ｔｒ＠ｅの
検索が行なわれる。
プ７０ツブｎ 、 ７１’がいずれもオフ状態にあり（
手順’ｆ／３ ） 、レジスタ３乙に保持された分岐ポ
インタ７１−２を取り出して、前述したようにして次の
節データの検索に移る。このような動作が該当キーが検
出されるか葉に到達するまで繰返されてＢ−ｔｒ＠ｅの
検索が行なわれる。
以上説明したように本発明によれば、補助記憶装置にＢ
−ｔｒｓ・を検索する機能を付加したので、Ｂ−ｔｒ＠
ｅを用いたデータ管理を実現する場合、ホスト計算機は
検索キーと検索命令を神助記憶装置に転送するだけで検
索結果が得られる。すなわち、補ホスト計算機の主記憶
装置、中央処理装置等の資源は一際占有されることがな
い。従って、本発明検索装置を適用した情報処理装置に
於いては、スループット、レスポンスタイム等が大幅に
改善される。更に、ホスト計算機と補助記憶装置間を結
ぶパス上のデータ転送量を大幅に減少させることができ
、バスを共有する付加装置が多い場合等においては、本
発明は特に有効である。
−ｔｒｓ・を検索する機能を付加したので、Ｂ−ｔｒ＠
ｅを用いたデータ管理を実現する場合、ホスト計算機は
検索キーと検索命令を神助記憶装置に転送するだけで検
索結果が得られる。すなわち、補ホスト計算機の主記憶
装置、中央処理装置等の資源は一際占有されることがな
い。従って、本発明検索装置を適用した情報処理装置に
於いては、スループット、レスポンスタイム等が大幅に
改善される。更に、ホスト計算機と補助記憶装置間を結
ぶパス上のデータ転送量を大幅に減少させることができ
、バスを共有する付加装置が多い場合等においては、本
発明は特に有効である。
第１ｇはｍ次のＢ−ｔｒｅｅの例を示すｍ１ｉｔｉ、第
２図は本発明検索装置の一例を示す構成図、第３図はそ
の補助記憶装置の構成図、第参図はその制御部の構成の
一例を示すブロック図、第一図は同じくその制御部の動
作を説明するためのタイミングチャート、第一図は本発
明の検索の過程を示す７ｐ−チャート、第７図はｍ次の
節データの構成図である。 ／・・・節、 コ・・・分岐ポインタ、
／／・・・ホスト計算機、／２・・・主記憶装置、１３
・・・中央処理装置、／Ｆ・・・データバス、／１・・
・補助記憶装置、 １・・・制御部、ｎ・・・記憶
部、３／・・・レジスタ、３ノ・・・比較器、３３・・
・７リツプ７０ツブ、３ダ・・・７リツプフロツプ、３
３・・・レジスタ、３ぶ・・・レジスタ、 〃
・・・節データ、！／−／・・−分岐ポインタ、ｊ／−
−？・・・分岐ｌインタ、ｊλ−７・・・キー、
ｊ２−２・・・キー、φｌ・・・り胃ツク、
φコ・・・クロック、Ｔｌ・・・タイミング、７０
・・・節データ、７／ −／・・・分岐ポインタ、７１
−２・・・分岐ポインタ、７Ｊ−／・・・キー、−７２
−一・・・キー。 特許出願人 キャノン株式会社 第１図 ／ 第２図 第３図
２図は本発明検索装置の一例を示す構成図、第３図はそ
の補助記憶装置の構成図、第参図はその制御部の構成の
一例を示すブロック図、第一図は同じくその制御部の動
作を説明するためのタイミングチャート、第一図は本発
明の検索の過程を示す７ｐ−チャート、第７図はｍ次の
節データの構成図である。 ／・・・節、 コ・・・分岐ポインタ、
／／・・・ホスト計算機、／２・・・主記憶装置、１３
・・・中央処理装置、／Ｆ・・・データバス、／１・・
・補助記憶装置、 １・・・制御部、ｎ・・・記憶
部、３／・・・レジスタ、３ノ・・・比較器、３３・・
・７リツプ７０ツブ、３ダ・・・７リツプフロツプ、３
３・・・レジスタ、３ぶ・・・レジスタ、 〃
・・・節データ、！／−／・・−分岐ポインタ、ｊ／−
−？・・・分岐ｌインタ、ｊλ−７・・・キー、
ｊ２−２・・・キー、φｌ・・・り胃ツク、
φコ・・・クロック、Ｔｌ・・・タイミング、７０
・・・節データ、７／ −／・・・分岐ポインタ、７１
−２・・・分岐ポインタ、７Ｊ−／・・・キー、−７２
−一・・・キー。 特許出願人 キャノン株式会社 第１図 ／ 第２図 第３図
Claims (1)
- 検索すべき情報を入力する入力手段および検索命令手段
を有するホスト計算機と、各種情報をＢ −ｔｒ＠・の
形態で格納した記憶手段および前記入力手段と前記検索
命令手段とにより前記各種情報を検索する検索手段を有
する補助記憶装置とを具備したことを特徴とする検索装
置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP56195535A JPS5897742A (ja) | 1981-12-07 | 1981-12-07 | 検索装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP56195535A JPS5897742A (ja) | 1981-12-07 | 1981-12-07 | 検索装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS5897742A true JPS5897742A (ja) | 1983-06-10 |
Family
ID=16342701
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP56195535A Pending JPS5897742A (ja) | 1981-12-07 | 1981-12-07 | 検索装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS5897742A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0689215A (ja) * | 1992-04-27 | 1994-03-29 | Internatl Business Mach Corp <Ibm> | 情報検索用コンピュータシステム及び同システムの記憶装置の操作方法 |
-
1981
- 1981-12-07 JP JP56195535A patent/JPS5897742A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0689215A (ja) * | 1992-04-27 | 1994-03-29 | Internatl Business Mach Corp <Ibm> | 情報検索用コンピュータシステム及び同システムの記憶装置の操作方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Morrison | PATRICIA—practical algorithm to retrieve information coded in alphanumeric | |
| US5442350A (en) | Method and means providing static dictionary structures for compressing character data and expanding compressed data | |
| Amble et al. | Ordered hash tables | |
| US8255398B2 (en) | Compression of sorted value indexes using common prefixes | |
| KR100529995B1 (ko) | 데이터베이스에 엘리먼트를 저장하는 방법 | |
| CN106980665B (zh) | 数据字典实现方法、装置及数据字典管理系统 | |
| Aoe et al. | A trie compaction algorithm for a large set of keys | |
| US7603346B1 (en) | Integrated search engine devices having pipelined search and b-tree maintenance sub-engines therein | |
| EP0720107B1 (en) | Word retrieval apparatus for a dictionnary | |
| US7653619B1 (en) | Integrated search engine devices having pipelined search and tree maintenance sub-engines therein that support variable tree height | |
| Buchsbaum et al. | Confluently persistent deques via data-structural bootstrapping | |
| CN100334582C (zh) | 在手持装置中存储和检索数据的方法及装置 | |
| Ahuja et al. | An associative/parallel processor for partial match retrieval using superimposed codes | |
| Lee | A word-parallel, bit-serial signature processor for superimposed coding | |
| Fisher | Copying cyclic list structures in linear time using bounded workspace | |
| JPS5897742A (ja) | 検索装置 | |
| Lee | ALTEP—A cellular processor for high-speed pattern matching | |
| Bercea et al. | An extendable data structure for incremental stable perfect hashing | |
| JP2675958B2 (ja) | 情報検索用計算機システム及びその記憶装置の動作方法 | |
| Campi et al. | Content addressable memory system concepts | |
| Du | Binary search in a multiprocessing environment | |
| Pissis et al. | Text Indexing for Long Patterns using Locally Consistent Anchors | |
| JP2615046B2 (ja) | レコード追加処理方法 | |
| JPS60160444A (ja) | リスト処理方法 | |
| Ouksel et al. | Concurrency in multidimensional linear hashing |