【事件の表示】
　特許第２９４３３０８号「Ｂ木インデックス検索方法」の請求項１に係る特許に対する特許異議の申立てについて、次のとおり決定する。
【結　論】
　訂正を認める。
　特許第２９４３３０８号の請求項１に係る特許を取り消す。
【理　由】
１． 手続の経緯
　本件特許第２９４３３０８号の請求項１に係る発明についての出願は、平成２年１０月２３日に出願され、平成１１年６月２５日にその発明について特許権の設定登録がなされ、その後異議申立人荒尾清により特許異議の申立てがなされ、取消しの理由が通知され、その指定期間内である平成１２年７月２５日に訂正の請求がされ、さらに第２回目の取消しの理由が通知されたものである。
２． 訂正の適否について
　平成１２年７月２５日付けの訂正請求に係る訂正事項ａ及びｂは、特許請求の範囲の減縮を目的とした明細書の訂正に該当し、いずれも、新規事項の追加に該当せず、実質的に特許請求の範囲を拡張又は変更するものではない。
　したがって、上記訂正は、特許法第１２０条の４第２項及び同条第３項で準用する第１２６条第２項及び第３項の規定に適合するので、当該訂正は認められるものである。
３．特許異議の申し立てについて
　本件特許第２９４３３０８号の請求項１に係る発明は、上記訂正に係る訂正明細書及び図面の記載からみて、その特許請求の範囲の請求項１に記載されたとおりのものであると認める。
 これに対して、平成１３年１月９日付けで取消理由を通知し、期間を指定して意見書を提出する機会を与えたが、特許権者からは何らの応答もない。
　そして、上記の取消理由は妥当なものと認められるので、本件特許は、この取消理由によって取り消すべきものである。
　よって、結論のとおり決定する。
【異議決定日】
平成１３年５月２４日（２００１．５．２４）
【訂正の要旨】
　訂正の要旨
　▲１▼訂正事項ａ
　特許請求の範囲の請求項１の記載事項である
「根、節および葉をそれぞれ構成する各部分木をページとして構成されるＢ木により編成され、各ページが所定個数の検索情報から成り、各検索情報がキー情報とデータからなるインデックスを検索するＢ木インデックス検索方法において、」
を、
「根、節および葉をそれぞれ構成する各部分木をページとして階層的に構成されるＢ木により編成され、各ページが所定個数の検索情報から成り、各検索情報がキー情報とデータからなるインデックスを検索するＢ木インデックス検索方法において、」
と訂正する。
　▲２▼訂正事項ｂ
　特許請求の範囲の請求項１の記載事項である
「前記キー情報に他の同一キー情報と区別する区別情報を付与したインデックスにより、前記区別情報を付与されたキー情報を検索キーとして前記検索情報を検索することを特徴とするＢ木インデックス検索方法」
を、
「前記キー情報に他の同一キー情報と相対的に区別する区別情報を付与したインデックスにより、前記区別情報を付与されたキー情報を検索キーとして前記検索情報を検索し、検索キーとキー情報が一致した際には前記区別情報の大小関係により上位階層ページから下位階層ページ方向に順次検索することを特徴とするＢ木インデックス検索方法。」
と訂正する。
（５４）【発明の名称】
Ｂ木インデックス検索方法
（５７）【特許請求の範囲】
　根、節および葉をそれぞれ構成する各部分木をページとして
階層的に
　前記キー情報に他の同一キー情報と
相対的に
を検索し、検索キーとキー情報が一致した際には前記区別情報の大小関係により上位階層ページから下位階層ページ方向に順次
【発明の詳細な説明】
［産業上の利用分野］
　本発明は、Ｂ木インデックスを検索するＢ木インデックス検索方法に関する。
［従来の技術］
　従来、コンピュータシステムにおいてデータベースを管理する場合、データベースは記憶装置に記憶される。そして、記憶したデータをマイクロプロセッサ等からなる制御装置により検索して目的のデータを得ている。またその記憶装置に記憶されているデータベースのデータの変更、消去等の管理も上記同様に制御装置により目的とするデータが検索されて行なわれる。
　上記の検索方法は種々あり、シーケンシャル検索、ダイレクト検索、Ｂ木検索等が知られている。シーケンシャル検索は全データを先頭から順次検索する方式であるのに対し、Ｂ木による検索は検索対象となるキー情報が含まれている階層のデータのみを検索する方式である。従ってＢ木による検索はシーケンシャル検索よりも処理が迅速に行なえる利点がある。また、ハッシュ法、逆インデックス法等のダイレクト検索は所定の函数と定数とに基づいて算出されたアドレスにより検索する方式である。上記定数はデータが格納される記憶領域のアドレスと記憶容量に基づいて予め設定されており変更することができない。このため将来データが増加したときに備えて記憶容量を予め非常に大きく設定しておかなくてはならない。一方Ｂ木による検索は各データのアドレスを上位階層のページのリンク情報で指示される。従ってＢ木による検索は記憶容量に大きく制約されることがない点でインデックス構築上簡便であり、経済的である。
　第５図は上記記憶装置に記憶されるＢ木構造のデータベースを模式的に示した図である。Ｂ木の構造は根、節（又は節点）、及び葉の三つの階層（レベル）から成り、各階層は部分木（ページ）（Ｐ（１）〜Ｐ（９））から成る。各ページの内部構成第６図（ｂ）に示す。各ページには、キーの値「ｘｉ（ｉ＝１，２・・・ｍ）」から成るキー部Ｄ１と、そのキーの値に対応するデータ「ａｉ（ｉ＝１，２・・・ｍ）」とから成るデータ部Ｄ２の２個１対に形成されたｍ個のデータＭｎ（ｎ＝１，２………ｍ）があり、そのｍ個のデータＭｎがキー部Ｄ１のキーの値の順に整列している。また、先頭データＭ１の前、各データＭｎとデータＭｎの間、及び末尾データＭｍの後にリンク情報「ｐｊ（ｊ＝０，１，２・・・ｍ）」から成るリンク部Ｒが設けられている。
　第６図（ａ）に、Ｂ木構造で編成された各国の機関車についてのデータベースの一例を示す。ページ（１）は上記Ｂ木構造の根の部分木である。ページ（２）並びにページ（３）は葉の部分木である。同図（ａ）には節の部分木は示していない。
　ページ（１）はデータＭＡ´（以下、各ページの該当部分を末インデックスと称する）と、２個のリンク部Ａ１，４及び未使用部Ａ５から成る。末インデックスＭＡ´のキー部Ａ２にはキー情報「３０３８」が格納され、データ部Ａ３にはデータ「フランス強力機関車」が格納されている。リンク部Ａ１には当該ページの末インデックスＭＡ´の値より小さな末インデックスの値を有するページ（２）を指すリンク情報「２」が格納され、リンク部Ａ４には、当該ページの末インデックスＭＡ´の値より大きな末インデックスの値を有するページ（３）を指すリンク情報「３」が格納されている。また、ページ（２）は、２個の末インデックスＭＢ´−１，Ｂ´−２と、３個のリンク部Ｂ１，Ｂ４，Ｂ７、及び未使用部Ｂ８とから成る。その末インデックスＭＢ´−１のキー部Ｂ２にはキー情報「３０３４」が格納され、データ部Ｂ３にはデータ「ドイツ多目的機関車」が格納されている。また、末インデックスＭＢ´−２のキー部Ｂ５にはキー情報「３０３５」が格納され、データ部Ｂ６にはデータ「イタリア電気機関車」が格納されている。リンク部Ｂ１，４、及びＢ７には当該ページが葉のページであるためリンク情報は格納されていない。また、ページ（３）は、ページ（２）と同様の構成であるが、末インデックスとしては、末インデックスＭＣ´１個のみを有している。なお、各ページの未使用部は、将来末インデックスを追加する際にその追加する末インデックスとリンク部を書き込むための予備領域である。
　上記Ｂ木の構造は、データ部に上記「イタリア電気機関車」のように具体的データが格納され、データファイル全体がそのままインデックスを構成するものと、具体的データの代りに更に詳細・多量なデータから成るデータファイルヘのアドレスポインタが格納され、データファイルから分離したインデックスを構成するものとがある。また、上記の二つの形式が混在した形のものもある。
　次に、上記構成のデータベース（インデックス）に対して前記制御装置により行なわれるデータの検索を、キー情報「３０３５」を有するデータを検索する場合を例として説明する。先ず、検索は「３０３５」を検索キーとして根の部分木（１ページ）から始まる。制御装置はベージ（１）を読み、検索キー「３０３５」とページ（１）のキー部Ａ２の値「３０３８」とを比較する。この例では検索キー「３０３５」が、ページ（１）のキー部Ａ２の値「３０３８」より小さいので、検索キーの値はキー部Ａ２の値より小さいと判別する。このように小さいと判別した場合は、続いてリンク部Ａ１のリンク情報「２」を読み出す。このリンク部Ａ１のリンク情報「２」はキー部Ａ２の値より少さいキー部の値を有する末インデックスを格納されたページを示している。制御装置は、その読み出されているリンク情報「２」で指示されるページ（２）を読む。そして、先ず、先頭末インデックスＭＢ´−１のキー部Ｂ２の値「３０３４」と検索キー「３０３５」とを比較する。この比較の結果は双方一致しない。このように一致しない場合は、続いて、隣接する末インデックスＭＢ´−２のキー部Ｂ５の値「３０３５」と検索キーとを比較する。この結果は検索キー「３０３５」と一致する。従って、その一致したキー情報「３０３５」を有する末インデックスＭＢ´−２を読み出す。このようにして「イタリア電気機関車」を捜し出すことができる。
　通常データベースを構成するデータの個数は極めて多数である。したがってそのデータベースから構築されるＢ木構造は多数の筋レベルのページを有し、また各節レベルのページに対応する葉レベルのページも多い。またデータベースは同一のキー情報を持つデータ（末インデックス）を多数含んでいる場合が多い。このため、検索は必ずしも第６図で説明したように簡単ではない。
　第５図はデータの個数が多く、かつ同一のキー情報を持つデータ（末インデックス）を多数含んでいるＢ木構造のデータベースの例を示したものである。各ページの中で、根のページＰ（１）のキー部１９、節のページＰ（８）、Ｐ（９）のキー部１３，１６，２２、葉のページＰ（２）、Ｐ（３）、Ｐ（４）及びＰ（５）のキー部１１，１２，１４，１５，１７，１８，２０及び２１は、それぞれが互いに同一のキー情報「Ａ」を有している。
　上記のようなＢ木構造のデータベースが記憶装置に記憶されているものとして、ページＰ（５）の末インデックスＭ１０を検索する場合について説明する。検索は、「Ａ」をキーとして、根のページＰ（１）から開始される。制御装置は先ずページＰ（１）のキー部１９のキー情報「Ａ」と検索キー「Ａ」と比較する。この比較の結果、キー部１９のキー情報「Ａ」と検索キー「Ａ」とは一致する。一致していると判別したときは、さらにリンク部Ｐ（１）−１を参照する。リンク部Ｐ（１）−１にはリンク情報「８」が格納されている。リンク部（１）−１にリンク情報が格納されていれば、そのリンク情報で示されるページには、他にもまだ検索キー「Ａ」と一致するキー情報を持つ末インデックスが格納されている可能性がある。そしてキー情報が検索キー「Ａ」と一致しているときには末インデックスの値も検索中の末インデックスＭ１０の値と一致する可能性がある。このため、制御装置は上記リンク部Ｐ（１）−１リンク情報「８」で指示されるページＰ（８）を読む。ページＰ（８）では、末インデックスＭ３のキー部１３のキー情報「Ａ」と検索キー「Ａ」とを比較する。ここでも比較の結果は双方一致するので、上記と同様に、さらにリンク部Ｐ（８）−１を参照する。リンク部Ｐ（８）−１にはリンク情報「２」が記憶されている。従って、上記ページＰ（１）の場合と同様の可能性によりそのリンク部Ｐ（８）−１のリンク情報「２」で指示されるページＰ（２）を読む。そして、末インデックスＭ１のキー部１１のキー情報「Ａ」と検索キー「Ａ」とを比較する。ここでもキー部１１のキー情報「Ａ」と検索キー「Ａ」とが一致するので上記と同様に、ページＰ（２）のリンク部Ｐ（２）−１を参照する。しかし、ページＰ（２）のリンク部Ｐ（２）−１にはリンク情報がない。リンク情報がないときは、これより下レベルの検索ルートはないと判別し、当該ページの末インデックスＭ１と検索中のインデックスＭ１０とを比較する。この結果は末インデックスＭ１と検索中の末インデックスＭ１０とは一致しない。一致しないときは、次に、同じベージの末インデックスＭ２を調べる。この末インデックスＭ２のキー部１２のキー情報は「Ａ」であり検索キーと一致するが、ここでも、そのリンク部Ｐ（２）−２，（２）−３には共にリンク情報が格納されていない。従って、これより下レベルの検索ルートはないと判別し、末インデックスＭ２と検索中のインデックスＭ１０とを比較する。この結果は末インデックスＭ２と検索中のインデックスＭ１０とが一致しないので、再びページＰ（８）を調べる。
　ページＰ（８）では、上述したように末インデックスＭ３のキー部１３のキー情報は「Ａ」であるが、リンク部Ｐ（８）−１のリンク情報「２」で指示されるページＰ（２）は検索済みであるので、末インデックスＭ３を検索中のインデックスＭ１０と比較する。末インデックスＭ３と検索中のインデックスＭ１０とが一致しないと判別すれば、次の末インデックスＭ６を調べる。末インデソクスＭ６のキー部１６のキー情報は「Ａ」であり、検索キー「Ａ」と一致する。一致した場合は上述してきたように続いてリンク部Ｐ（８）−２を参照する。リンク部Ｐ（８）−２にはリンク情報「３」が記憶されている。従って前記と同様の可能性により、そのリンク部Ｐ（８）−２のリンク情報「３」で指示されるページＰ（３）を読み、読んだページＰ（３）の末インデックスＭ４を調べる。
　上記のようにして検索をページＰ（１）→Ｐ（８）→Ｐ（２）→Ｐ（８）→Ｐ（３）→Ｐ（８）→Ｐ（４）→Ｐ（８）→Ｐ（１）→Ｐ（９）→Ｐ（５）の順に行なって、検索中の末インデックスＭ１０が読み出される。
［発明が解決しようとする課題］
　このように、同一のキー情報を有する末インデックスを検索する場合の検索ルートは、上のレベルから下のレベルへと一筋に流れず、上から下へ、下から上へ、また上から下へと複雑で多くの時間を必要とする。特に削除や修正をするようなとき１個の末インデックスを読み出す場合は時間が掛かりすぎるという問題がある。これは、複数の末インデックス（検索情報）にキー情報が同一なものが存在することに起因すると考えられる。
　してみれば、キー情報が同一な検索情報に対して相対的に区別できるようにすれば、キー情報が同一である検索情報に対する複雑で時間を要する検索を防止でき、迅速な検索を実現できると考えられる。
　この発明の課題は、キー情報が同一な検索情報に対して各キー情報を相対的に区別して前記検索情報を検索できるようにすることである。
［課題を解決するための手段］
　本発明は、根，節および葉をそれぞれ構成する各部分木をページとして構成されるＢ木により編成され、各ページが所定個数の検索情報から成り、各検索情報がキー情報とデータとからなるインデックスを検索するＢ木インデックス検索方法において、前記キー情報に他の同一キー情報と区別する区別情報を付与したインデックスにより、前記区別情報を付与されたキー情報を検索キーとして前記検索情報を検索することを特徴とする。
［実施例］
　以下、一実施例を第１図〜第４図を参照して説明する。
　第１図は本実施例におけるコンピュータシステムのブロック図である。記憶装置１は磁気デスクから成り、後で詳しく述べる第２図に示すＢ木で編成されたインデックス（Ｂ木インデックス１ａ）を記憶する。中央処理装置２はマイクロプロセッサ等から成り、前記Ｂ木で編成されたインデックス去検索する。
　第２図に上記記憶装置１に記憶されるＢ木インテックスの構築例を模式的に示す。根のページＰ１、節のページＰ８，Ｐ９、葉のページＰ２，Ｐ３，Ｐ４及びＰ５のキー部は、それぞれ互いに同一のキー情報「Ａ」を有している。ただし、第５図で説明した従来例とは異なり、本実施例では各キー部をユニークにするための相対的なレコード番号が各キー部に付与されている。例えば第２図に示すようにＰ１のキー部１９´は実際のキー情報「Ａ」に相対レコード番号「９」が付与されている。同様に、ページＰ８のキー部１３´及びキー部１６´は実際のキー情報「Ａ」に相対レコード番号「３」及び「６」が付与されている。また、ページＰ９のキー部２２´も実際のキー情報「Ａ」に相対レコー’ド番号「１２」が付与されている。
　同様にページＰ２〜ページＰ５の全てのキー部はキー情報「Ａ」に相対レコード番号（１，２，４，５，７，８，１０，１１）が付与されている。この構成において、例えばキー情報が「Ａ」で相対レコード番号「８．５」である末インデックスが発生した場合は、相対レコード番号「８」を有する末インデックス即ちページＰ４のキー部１８´を有する末インデックスの後方未使用部にその新たな末インデックスを追加する。さらに、キー情報が「Ａ」の末インデックスが新たに多数発生した場合、例えば相対レコード番号が「８．６」、「８．７」、「８．８」、「８．９」である４個の末インデックスが発生した場合は、新たに葉のページ例えばページＰ４−５を作成し、その作成したページＰ４−５に上記発生した相対レコード番号が「８．６」〜「８．９」である４個の末インデックスを格納する。そして、前記ページＰ４に先に新たに追加した相対レコード番号「８．５」の末インデックスの後方のリンク部にリンク情報を格納する。そのリンク情報は上記新たに作成されたページＰ４−５を示すものである。この場合前記ページＰ４はリンク部にリンク情報を格納されて節のページとなり、従って節のページＰ８の下のレベルに更に節のページＰ４がある形となり、当該インデックスは節のレベルが１層から２層構造に展開したものになる。
　第３図は、上記Ｂ木を構成する各部分木（ページ）の内部構成図である。各ペ一ジには、キーの値「ｘ´ｉ（ｉ＝１，２・・・ｍ）」から成るキー部Ｄ´１と、そのキーの値に対応するデータ「ａ´ｉ（ｉ＝１，２・・・ｍ）」とから成るデータ部Ｄ´２の２個１対に形成されたｍ個のデータＭ´−ｎ（ｎ＝１，２・・・ｍ）があり、そのｍ個のデータＭ´−ｎがキー部Ｄ´１のキーの値の順に整列している。その整列している先頭データＭ´−１の前、各データＭ´−ｎとデータＭ´−ｎの間、及び末尾データＭ´−ｎの後にリンク情報「ｐ´ｊ（ｊ＝０，１，２・・・ｍ）」から成るリンク部Ｒ´が設けられている。上記キー部Ｄ１１はＤ´１−１、及びＤ´１−２で示す二つの情報領域に内部分割されている。そしてＤ´１−１で示す前方の情報領域には実際のキーの値Ｘｉが格納されている。また、Ｄ´１−２で示す後方の情報領域には相対レコード番号ＲＣｉが記憶されている。
　第４図は、記憶装置１に記憶されている上記第２図及び第３図で説明した構成のキー部を有するデータ（末インデックス）から成るＢ本編成のインデックスに基づいて、中央処理装置２により行なわれる検索処理の動作を説明するフローチャートである。尚、上記末インデックスのキー部は上述したようにキー情報の直後に相対レコード番号が付加（ユニーク化）されている。従ってキー部全体の値を見ると互いに同一のものはインデックス中に存在しない。また、上記フローチャートで示される動作は特に図示しない操作パネル等からユニークとなっている検索キーと共に検索指令が中央処理装置２に対して与えられることにより開始される。
　上記検索を開始すると、中央処理装置２は記憶装置１に記憶されているインデックスの根のページを読む（Ｓ１）（検索は先ず根のページから開始される）。
　中央処理装置２は、読んだページの末インデックスのキー部の値と、前記動作開始前に与えられた検索キーの値とを比較する（Ｓ２）。そして、検索キーの値が末インデックスのキー部の値より小さければ、その末インデックスの直前に設けられているリンク部を参照する（Ｓ３）。そのリンク部にリンク情報が格納されていれば、そのリンク情報により指示されている下のレベルのページを読む（Ｓ４）。続いて、処理Ｓ２に戻っで、再びその読んだページの末インデックスのキー部の値と検索キー値を比較する。
　即ち、検索キーの値が検索されたページの末インデックスのキー部の値より小さければ、前記末インデックスの直前に設けられているリンク部に格納されているリンク情報により指示される下のレベルのページが検索される。
　前記処理Ｓ２で、検索キーの値の方が大きければ、当該ページ内で当該末インデックスの後方に他に末インデックスが格納されているか否か判別する（Ｓ６）。他に末インデックスが格納されていれば、その末インデックスのキー部の値と検索キーの値とを比較する（Ｓ２）。
　即ち、検索中のページに複数の末インデックスがある場合、先頭の末インデックスが検索中のものでなければ次の末インデックスへと順次そのキー部の値を読み取って検索キーの値と比較する。
　前記処理Ｓ６で、後方に他に末インデックスが格納されていなければ、当該末インデックスの直後に位置するリンク部を参照する（Ｓ７）。そのリンク部にリンク情報が格納されていれば、そのリンク情報により指示されている下のレベルのページを読む（Ｓ９）。続いて、処理Ｓ２に戻って、再びその読んだページの末インデックスのキー部の値と検索キーの値を比較する。
　即ち、検索キーの値が検索されたページの末インデックスのキー部の値より大きければ、前記末インデックスの直後に設けられたリンク部に格納されているリンク情報により指示される下のレベルのページが検索される。
　前記処理Ｓ２で、検索キーの値が一致すれば、その検索キーの値と一致するキー部を有する末インデックスを読み出し（Ｓ１０）、処理を終了する。
　上述したように、検索キーの値と末インデックスのキー部の値とが一致しないときは常に更に下のレベルの節または葉のページべと検索を進め、上のレベルに戻ることはない。
　尚、前記処理Ｓ３で、参照したリンク部にリンク情報が格納されていなければ、それより先に進む検索ルートはないため該当する末インデックスは存在しない。この場合は末インデックスは存在しない旨の処理を行って（Ｓ５）、検索を終了する。また、前記処理Ｓ７で、参照したリンク部にリンク情報が格納されていなければ、それより先に進む検索ルートはないため該当する末インデックスは存在しない。この場合も末インデックスは存在しない旨の処理を行って（Ｓ８）、検索を終了する。上記処理Ｓ５または処理Ｓ８の処理は、例えば「該当なしフラグ」の設定、特に図示しない表示装置に直接「該当なし」の表示制御を行う等の処理である。
　上記のようにして行われる検索処理について、さらに第２図に示す同一のキー情報を有する複数の検索情報（末インデックス）を多数含む構成のインデックスにおいて、同一のキー情報を有する特定の末インデックス側えば同図ページＰ５の末インデックスＭ１０´を検索する場合を説明する。
　検索は、「Ａ」をキーとして、根のページＰ１から開始される。中央処理装置２は先ず、ページＰ１を読み、ページＰ１の末インデックスＭ１９´のキー部１９´のキー情報「Ａ」と検索中の末インデック、スＭ１０´のキー情報「Ａ」とを比較する。この比較の結果、検索中の末インデックスＭ１０´のキー情報「Ａ」は末インデックスＭ１９´のキー部１９´のキー情報「Ａ」と一致する。一致した場合は、続いて末インデックスＭ１９´のキー部１９´に付与されている相対レコード番号「９」と検索中の末インデックスＭ１０´のキー部２０´に付与されている相対レコード番号「１０」とを比較する。この比較の結果は末インデックスＭ１９´のキー部１９´に付与されている相対レコード番号「９」より検索中の末インデックスＭ１０´のキー部２０´に付与されている相対レコード番号「１０」のほうが大きい。その場合は末インデックスＭ１９´の直後にあるリンク部Ｐ１−２を参照する。このリンク部には末インデックスＭ１９´の相対レコード番号より大きい相対レコード番号を有する末インデックスを含むページを示すリンク情報「９」が格納されている。そのリンク情報「９」の指示により、ページＰ９を読む。そして、ページＰ９の末インデックスＭ２２´のキー部２２´のキー情報「Ａ」と検索中の末インデックスＭ１０´のキー情報「Ａ」と比較する。これらの情報は一致するので、上記と同様にして続いて末インデックスＭ２２´のキー部２２´に付与されている相対レコード番号「１２」と検索中の末インデックスＭ１０´のキー部２０´に付与されている相対レコード番号「１０」とを比較する。この比較の結果は末インデックスＭ２２´のキー部２２´に付与されている相対レコード番号「１２」より検索中の末インデックスＭ１０´のキー部２０´に付与されている相対レコード番号「１０」のほうが小さい。小さい場合は、末インデックスＭ２２´の直前にあるリのほうが大きい。その場合は末インデックスＭ１９´の直後にあるリンク部Ｐ１−２を参照する。このリンク部には末インデックスＭ１９´の相対レコード番号より大きい相対レコード番号を有する末インデックスを含むページを示すリンク情報「９」が格納されている。そのリンク情報「９」の指示により、ページＰ９を読む、そして、ページＰ９の末インデックスＭ２２´のキー部２２´のキー情報「Ａ」と検索中の末インデりクスＭ１０´のキー情報「Ａ」と比較する。これらの情報は一致するので、上記と同様にして続いて末インデックスＭ２２´のキー部２２´に付与されている相対レコード番号「１２」と検索中の末インデックスＭ１０´のキー部２０´に付与されている相対レコード番号「１０」とを比較する。この比較の結果は末インデックスＭ２２´のキー部２２´に付与されている相対レコード番号「１２」より検索中の末インデックスＭ１０´のキー部２０´に付与されている相対レコード番号「１０」のほうが小さい。小さい場合は、末インデックスＭ２２´の直前にあるリシク部Ｐ９−１を参照する。このリンク部には末インデックスのＭ２２´の相対レコード番号より小さい相対レコード番号を有する末インデックスを含むページを示すリンク情報「５」が格納されている。そのリンク情報「５」の指示により、ページＰ５���読む。そして、ページＰ５のキー部２０´のキー情報「Ａ」と検索中の末インデックスＭ１０´のキー情報「Ａ」と比較する。この比較の結果は双方一致するので、続いてページＰ５のキー部２０´に付与されている相対レコード番号「１０」と検索中の末インデックスＭ１０´のキー部２０´に付与されている相対レコード番号「１０」とを比較する。この比較の結果も双方一致する。従って、ページＰ５の末インデックスＭ１０´が検索中の末インデックスＭ１０´であると判断し、その末インデックスＭ１０´を読み出す。
　このように、Ｐ１→Ｐ９→Ｐ５のように上のレベルから下のレベルへと最短の動作で検索し、所望の末インデックスを読み出すことができる。そして、この後、削除または修正等の処理を直ちに行なうことができる。
　尚、上記実施例では、同一なキー情報を有するキー部をユニークとするために相対レコード番号を用いているが、これは相対レコード番号に限ることなく同一なキー情報を有するキー部を相対的にユニークとするようなデータであればよい。また相対的データを付加する記憶領域の位置をキー情報の直後にしているが当該末インデックスの末尾、或いはデータ部内等種々考えられる。
　また、記憶装置を磁気デスクとしているがＲＯＭカード等の脱着自在なものでもよい。
［発明の効果］
　本発明によれば、Ｂ木により構成され、各検索情報がキー情報とデータとからなるインデックスを検索するＢ木インデックス検索方法において、キー情報が同一な検索情報に対して各キー情報を相対的に区別する区別情報を付与したインデックスにより、その区別情報を付与されたキー情報を検索キーとして前記検索情報を検索するので、キー情報が同一である検索情報に対する複雑で時間を要する検索を防止でき、迅速な検索を実現できる。
【図面の簡単な説明】
　第１図は一実施例のコンピュータシステムのブロック図、
　第２図は一実施例におけるＢ木で編成されたインデックスを説明する図、
　第３図は一実施例のＢ木のページの内部構成を示す図、
　第４図は中央処理装置２により行なわれる検索処理の動作を説明するフローチャート、
　第５図は従来のＢ木におけるデータファイルを模式的に示す図、
　第６図は従来のＢ木のページの内部構成を示す図である。
　１…記憶装置、
　２…中央処理装置