JPH1166096A - データ蓄積方法、そのデータ蓄積方法によって蓄積されたデータベース及びそのデータベースの検索方法 - Google Patents

Abstract

(57)【要約】 【課題】二分探索木構造で蓄積されたデータベースの検
索における無駄な検索時間を減らすと共に、情報検索の
データ構造として無駄なノードを作ることによるメモリ
の浪費を減らすことを目的とする 【解決手段】各ノードは、メモリアドレス０、メモリア
ドレス１、アドレスパタン情報及びビットパタン情報に
より構成される。ビットパタン情報はそのノードが判断
するビット位置を示し、アドレスパタン情報は、分岐の
条件式を与える。メモリアドレス０は、条件式が”偽”
の場合の次のノードを示し、メモリアドレス１は”真”
ノード場合の次のノード又は検索の情報を与える。本発
明は、ビットパタン情報とアドレスパターン情報によ
り、数ビットまとめて、検索アドレスの検査をすること
ができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データ蓄積方法、
そのデータ蓄積方法によって蓄積されたデータベース及
びそのデータベースの検索方法に関する。特に、回線交
換、ネットワークルータ等でネットワークアドレス、電
話番号等の数値化された情報に関連づけてルーティング
情報、加入者情報等をツリー状に蓄積し、その蓄積され
たデータベース中から、そのネットワークアドレス、電
話番号等の数値化されたデータをキーにしてルーティン
グ情報、加入者情報等の情報を二分探索木により検索す
る方法に関する。

【０００２】

【従来の技術】数値化されたネットワークアドレス情報
をキーにして経路情報を検索する従来の方法として、テ
ーブル検索による方法や二分探索による方法がある。前
者のテーブル検索法の場合は、図１のように、ネットワ
ークアドレス情報及び経路情報を１対１のテーブルとし
て持っておく。そして、この場合の検索は、テーブルを
先頭から比較し、条件に合致したアドレス情報を見つけ
た時点で検索を止める。後述するように経路情報量が多
くなった場合に、検索に多大な時間を要するために、後
者の二分探索法が一般的に用いられる。

【０００３】後者の場合は、数値化されたネットワーク
アドレス情報をもとに、ツリー状にノードを作成する。
各ノードには次のノードが格納されているメモリアドレ
スを二つ格納し，ツリーの一番最後のノードには経路情
報を格納しておく（図２）。このツリーを使って検索す
る場合は、図２の左の方からノードデータを読み出し、
キーとなるアドレスの先頭のビットを調べ、０であるな
らばそのノードの上側のノードを次のノードとして読み
だす。そうでない場合は、下側のノードを読みだす。そ
して、２番目のビット、３番目のビットというように、
上位のビットから順番に比較を繰り返し、最後にたどり
着いたところの経路情報を目的の経路情報として求め
る。

【０００４】

【発明が解決しようとする課題】従来のテーブル検索の
場合は、比較処理の回数の最大値は格納されている情報
数に等しい。そして、順番にテーブルの先頭から検索す
るため、情報数が多くなりそのテーブルが大きくなった
場合、比較の回数が非常に大きくなり、検索処理に多く
の時間を費やすという問題がある。

【０００５】一方、二分探索法では、この方法の場合の
最大検索回数は、検索キーのアドレスの大きさに依存す
る。つまりアドレスが８ビットであれば８回であり、ア
ドレスが３２ビットであれば３２回である。この場合
は、格納情報が増えても検索回数は増加しない。しか
し、アドレス情報として、H'8350、H'8351、H'8352、H'
8353、....、H'835E、H'835Fといった１６ビットのアド
レスとその経路情報が１６個だけ登録された場合、図３
のような二分探索木を形成する。このような場合は、多
くのネットワークで用いられているような、一つのネッ
トワークアドレスを複数のサブネットに分割して使用し
ている場合に頻繁に起こる。この例の場合、全ての経路
データは最初の１２ビットが同じであるため、ノード１
からノード１２の１２ノード分の「無駄な」メモリ領域
を使ってしまうだけでなく、検索時には、その１２個の
ノードをたどる無駄な検索処理が必要という問題もあ
る。

【０００６】そこで、本発明は、上記の問題点を解消
し、情報検索における無駄な検索時間を減らすと共に、
情報検索のデータ構造として無駄なノードを作ることに
よるメモリの浪費を減らすことを目的とする。

【０００７】

【課題を解決するための手段】本発明では、各ノードで
上位ビットから順次、分岐しつつ判断する二分探索木に
おいて、図３のように複数のノードで連続して分岐が無
い場合に、１ビットずつ分岐の判断をするのでなく、連
続した分岐の無いビットをまとめて（縮退して）図４の
ように分岐すると考える（なお、図４は、縮退ノード３
１が本発明によるものであり、その他は、必ずしも本発
明によるものとは限らないので、あくまでも縮退を説明
するための模試図である。）。そして、この縮退ノード
３１では、ノード１からノード１２の個々に行われた判
断を、縮退した全ビットをまとめて一回で判断する。そ
のために、縮退したビット列のビット位置（まとめて判
断されるビット位置）を示すビットパタン情報（検索ア
ドレスのビット列の中で、該当するビット位置に１を立
て、それ以外のビット位置は”０”とする）と、登録さ
れた検索アドレスに対して”真”と判断されるアドレス
パタン情報（検索アドレスのビット列の中で、縮退ビッ
ト位置では、登録されたアドレス情報の二値情報とし、
それ以外のビット位置は”０”とする）とを、縮退ノー
ド３１に設ける。ところで、登録されたアドレス ＡＮ
Ｄ ビットパタン＝アドレスパタンの関係となっている
ので、この縮退ノード３１で登録されたアドレス情報か
否かの判断ができる。従って、これを分岐条件として、
検索アドレス情報に対して、そのアドレスに応じて、分
岐させることができる。

【０００８】図４により、縮退ノード３１について、具
体的に説明すると、図５に示されるように、登録された
アドレス情報（これは検索アドレス、又はネットワーク
アドレスでもある。）がH'8350、H'8351、H'8352、H'83
53、....、H'835E、H'835Fであるので、二値情報として
は、全１６ビットのうち、上位１２ビットの部分は同じ
であって、分岐の必要は無い。そこで、上位１２ビット
をまとめて判断するために、全１６ビットのうち上位１
２ビットのみ１であるH'FFF0（１１１１１１１１１１１
１００００）をビットパタン情報としてノードに与え
る。一方、上記登録されたアドレス情報( つまりH'835
0、H'8351、H'8352、H'8353、....、H'835E、H'835F)
の縮退ビット位置（上位１２ビット）の二値情報は、図
５に示すように全て（１０００００１１０１０１）であ
るので、アドレスパタン情報として（１０００００１１
０１０１００００）を縮退ノード３１に設ける。この、
（１０００００１１０１０１００００）は、登録された
アドレス情報の一つであるH'8350のアドレスでもある。

【０００９】次にこの場合における縮退ノード３１での
検索は、次の通り行われる。いま、アドレスH'8352の検
索を考える。アドレスH'8352（１０００００１１０１０
１００１０）とノードのビットパタン情報（１１１１１
１１１１１１１００００）の論理積をとり、その値（１
０００００１１０１０１００００）とアドレスパタン情
報（１０００００１１０１０１００００）と比較する
と、一致する。従って、ノード３１は、”真”と判断し
て分岐する。図４の他の登録されたアドレスを選んで判
断しても、おなじ結果が得られる。従って、縮退ノード
３１で、H'8350、H'8351、H'8352、H'8353、....、H'83
5E、H'835Fの登録されたアドレス情報に対して、縮退ノ
ード３１でまとめて上位１２ビットの判断がなされ、検
索が進んだこととなる。

【００１０】以上を含めて一般的には、その分岐の無い
ノードをまとめて一つのノードに縮退し、縮退したビッ
トを示すビットパタン情報（図３では上位１２ビットを
まとめているのでH'FFF0(1111111111110000)) としてそ
の縮退ノード３１に付加する。そして、検索時に、検索
したいアドレス（この場合、アドレスは数値化され、0/
1 の二値データとして表現されている：数値化されたデ
ータ）とビットパタン情報（縮退されない場合は、その
ノードで判断するビット位置のみ１の二値データ、縮退
ノード３１の場合は、縮退したビット位置のみ１の二値
データ）との論理積をとり、その値( 縮退されない場合
は、そのノードの判断ビット位置の0/1情報、縮退ノー
ド３１の場合は、縮退したビット位置の0/1 情報が得ら
れる）とノードに付加されているアドレスパタン情報と
を比較し、一致した場合は、次のノードをたどり、不一
致の場合は、次の別のノードをたどるか又は検索を終了
する。

【００１１】

【発明の実施の形態】次に、本発明の実施例について説
明するために、８ビットのネットワークアドレスに経路
情報を関連づけたデータベースからネットワークアドレ
スをもとに経路情報を検索するシステムを考える。第６
図は、そのデータベースを検索するための二分探索木及
び各ノードの概略図である。図で登録されているのは、
ネットワークアドレス（＝登録されたアドレス情報＝検
索アドレス＝データベースのアドレス）（本発明のデー
タ蓄積、検索方法においては、アドレスは数値化され、
0/1 の二値データとして表現されている：数値化された
データ）H'24(00100100)、H'2E(00101110)、H'3C(00110
010)、H'CD(11001101)に関連する四つの経路情報であ
る。ツリー上の各分岐点には、図７に示す構成のノード
が配置されており、各ノードは、分岐を判定する条件式
が”偽”（ＦＡＬＳＥ）の場合に参照する次のアドレス
が格納されているメモリアドレス（メモリアドレス
０）、”真”（ＴＲＵＥ）の場合に参照するメモリアド
レス（メモリアドレス１）、アドレスパタン情報及びビ
ットパタン情報から構成されている。予めノードの領域
をメモリ上に確保し、ノード番号を割り振っている場合
は、”メモリアドレス０”と”メモリアドレス１”の代
わりに、そのノード番号を使用することも可能である。
なお、「二分探索木構造でデータを蓄積する」における
「データ」とは、図６における、二分探索木を構成する
ノードのデータ、経路情報及びこれと同等のものを指
す。

【００１２】アドレスパタン情報は、分岐を判定する条
件式となるものであり、縮退した場合は、その縮退部分
のビット位置のアドレスが”真”と判断されるアドレス
の二値情報である。ビットパタン情報は、前記二分探索
木のノードのうち分岐する先が一方向しか無いノードが
複数連続する場合は、前記一連のノード群を一つのノー
ドとし、該一連のノード群で検査すべきであったビット
位置の全てのビットを１にしそれ以外のビット位置のビ
ットを０にしたデータであり、前記二分探索木のノード
のうち分岐する先が一方向しか無いノードが複数連続し
ない場合は、そのノードで検査すべきビット位置のビッ
トを１にしそれ以外のビット位置のビットを０にしたデ
ータである。つまり、このビットパタン情報は、数値化
されたデータのビット列に対し当該ノードでの検査ビッ
ト位置に１を立てたもので、その検査ビット位置を示
す。

【００１３】アドレスパタン情報は、縮退しない場合
は、ビットパタン情報をそのまま使用することができ
る。また縮退している場合は、”真”として分岐される
ネットワークアドレスとビットパタン情報の論理積の結
果をその縮退ノードのアドレスパタン情報とする。な
お、縮退しない場合も、縮退した場合と同じように、ネ
ットワークアドレスとビットパタン情報の論理積からア
ドレスパタン情報を作成することもできる。

【００１４】縮退していないノードにもビットパタン情
報とアドレスパタン情報を付加することにより、縮退ノ
ードと同じように検索したいアドレスとビットパタン情
報との論理積と、アドレスパタン情報とを比較すること
により、分岐の判定が可能となる。なお、縮退していな
いノードには、上記のアドレスパタン情報とビットパタ
ン情報の代わりに分岐していないことを示す値（例え
ば”０”）を入れておくことができる。こうすることに
よって、次にどのノードに行くかを判定する前に、アド
レスパタン情報を検査し、その値が”０”ならば従来の
判定方法を適用して分岐を判定することができる。

【００１５】図６を簡単に説明する。ネットワークアド
レスH'24(00100100)、H'2E(00101110)、H'3C(0011001
0)、H'CD(11001101)の第１ビット目を見ると、H'24、H'
2E及びH'3Cが”０”であるのに、H'CDは”１”であるた
め、先頭のノード１（３２）で分岐が必要となり、次の
ノード（３３、３４）が格納されている二つのメモリア
ドレス、アドレスパタン情報及びビットパタン情報を付
加する。８ビットの先頭のビットを判断し分岐するので
あるから、ビットパタン情報としては、（１０００００
００）となる、これは、H'80であり、アドレスパタン情
報としても同じH'80を格納する。これにより、登録され
たアドレス情報とビットパタン情報の論理積を取ったも
のとアドレスパタン情報を比較すると、H'CDには、”
真”を与え、H'24、H'2E及びH'3Cには”偽”を与え
る。”真”のネットワークアドレスにはメモリアドレス
１からノード８（３３）のアドレスを与え、”偽”のネ
ットワークアドレスにはメモリアドレス０からノード２
（３４）のアドレスを与えて、分岐を行う。該ノード２
（３４）は、ノード１（３２）での判定が”偽”であっ
た場合、つまり、上位１ビット目が０であった場合の、
次の判定を行うためのノードである。上位１ビット目が
０になるのは、本実施の形態の場合は、H'24(0010010
0)、H'2E(00101110)、H'3C(00110010)、の三つである。
これらの三つのアドレスは、上位２ビット目と３ビット
目がそれぞれ０、１であるので、一つに縮退させること
ができる。従って、上位２ビット目と３ビットを縮退し
たことを示すために、ビットパタン情報として、上位２
ビット目と３ビット目を１として、残りのビットを０と
した値（H'60:01100000 ）を格納する。また上位２ビッ
トと３ビット目をそれぞれ０、１として、残りのビット
を全て０にしたもの（H'20:00100000 ）をアドレスパタ
ン情報として格納する。このアドレスパタン情報は、H'
24、H'2EあるいはH'3Cとビットパタン情報の論理積によ
って求めることできる。さらに、このノードのメモリア
ドレス０には、終点を示す値（例えば”０”）を入れて
おく。このようにすることによって、ここから先に該当
する情報が無いことがこの時点で判明し、無駄な検索を
中止することができる。メモリアドレス１には、ノード
３（３５）の番地を格納しておく。ノード３（３５）で
は、H'24、H'2E、H'3Cの三つのアドレスの中に上位４ビ
ット目が異なるものがあるため、分岐が生じる。したが
って、ここでは、ノード１（３２）を作ったのと同様に
ノード３（３５）を作る。以上の作業を四つのアドレス
分繰り返すことによって、図６のツリーを作ることがで
きる。図に示すように、最後になったノードには、経路
情報が格納されているメモリアドレスを格納しておき経
路情報を取り出すことができる。

【００１６】最後のノード、例えばノード８（３３）の
ビットパタン情報としては、先に分岐判定されたビット
以外のビット（この場合は、下位の７ビット）を”１”
とした情報（０１１１１１１１）つまりH'7Fをビットパ
タン情報とし、このビットパタン情報と検索されるアド
レス情報であるH'CD(11001101)の論理積を求め、その値
をアドレスパタン情報（０１００１１０１＝H'4D）とす
る。そして、メモリアドレス０には”０”を入れ、メモ
リアドレス１には、経路情報のアドレスを入れる。

【００１７】図８に、本発明の検索方式の概略フローチ
ャートを示す。このフローチャートをもとに、図６のツ
リーから与えられたアドレスに対する経路情報を検索す
る例を示す。先ず、ユーザ、外部等からネットワークア
ドレスH'2Eに対する経路情報検索の要求が来たとする。
最初にノード１（３２）のデータを読みだす。ノード１
（３２）では、H'2Eとビットパタン情報（H'80) との論
理積を計算し（H'00) アドレスパタン情報(H'80)と比較
する。この場合は一致しないので、メモリアドレス０を
参照し”０”でないので、その値の示すノード、つまり
ノード２（３４）のアドレスを読みだす。ノード２（３
４）においても、同じようにH'2EとH'60との論理積を計
算（H'20) し、H'20と比較する。一致するので、ノード
２（３４）のメモリアドレス１を参照し、ノード３（３
５）に進む。同様にしてノード４（３６）、ノード６
（３９）とたどり最後に経路情報２（４１）を検索する
ことができる。

【００１８】次に、このネットワークアドレスに登録さ
れていないネットワークアドレスH'5Eに対する経路情報
の要求が来たとする。先ず、ノード１（３２）では、H'
5EとH'80との論理積を計算（H'00) し、H'80と比較す
る。一致しないのでメモリアドレス０を参照し、ノード
２（３４）に進む。同じくノード２（３４）でH'5EとH'
60との論理積を計算（H'60) し、H'20と比較する一致し
ないのでメモリアドレス０を参照するが、メモリアドレ
ス０には”０”が格納されているので、ここで検索を終
了し、検索要求元に対して該当する経路情報が無いこと
を通知する。

【００１９】次に、経路情報を追加する手順を説明す
る。図９及び図１０にその概略フローチャートを示す。
また、図１１には、H'DFの経路情報を追加した後のツリ
ーを示す。図６のツリーにネットワークアドレスH'DFの
経路情報を追加する要求が来たとする。先ず、検索要求
時と同様に、ツリーを検索する。検査して若し見つかれ
ば、既に登録済みなので、登録済であるというエラーを
返して終了する。この場合、登録されていないので、検
索がノード１（３２）から開始される。ノード１（３
２）でH'DFとH'80との論理積が取られ、その値(H'80)と
ノード１（３２）のアドレスパタン情報H'80と比較さ
れ、一致するのでメモリアドレス1 を参照してノード８
（３３）に進む。ノード８（３３）では、H'DFとH'7Fと
の論理積が取られ、その値とノード８（３３）のアドレ
スパタン情報H'4Dと比較され、一致しないのでノード８
（３３）のメモリアドレス０を参照するがそこには”
０”が格納されており、検索は失敗に終わる。従って、
このノード８（３３）のところにノードを追加する必要
が有ることが判明する。ノード８（３３）に格納されて
いるビットパタン情報から、縮退が上位の何ビット目
（Ｎｕ）から何ビット目（Ｎｌ）までまとめられている
かを調べる。若し、縮退していなければ、新規のノード
を作り、そのノードに経路情報のアドレスを納め、か
つ、この新規のノードをノード８（３３）に接続して終
了する。この例では、ビットパタン情報が（０１１１１
１１１）であるので、２ビット目から８ビット目までが
縮退されているので、Ｎｕ＝２、Ｎｌ＝８となる。そこ
で、アドレスパタン情報H'4D（０１００１１０１）とH'
DF（１１０１１１１１）の上位から２ビット目から８ビ
ット目までを順番に比較し、最初に異なるところが分岐
ノードとなるので、そのビット数Ｎｂを求める。この例
では、４ビット目が異なるため、Ｎｂは４となる。

【００２０】次に、上位からＮｂビット目つまりこの例
では、４ビット目のノードを作成する。図１１では、ノ
ード１０（４６）に該当する。ノード１０（４６）で
は、４ビット目だけ判断するので、判断するビットであ
る上から４ビット目のみが”１”のアドレス（０００１
００００：H'10）をノード１０（４６）のビットパタン
情報とする。ノード１０（４６）は、縮退が無いことか
ら、アドレスパタン情報は、ビットパタン情報と同じH'
10とする。次にＮｕとＮｂを比較して等しくない場合
は、ノードを作成し、そうでない場合は、ノードを作ら
ずに、先程作成したノード１０（４６）のアドレスをノ
ード８（３３）の一つ手前のノードつまりノード１（３
２、４４）のメモリアドレス１に書き込む。しかし、こ
の例では、ＮｕとＮｂが等しくないのでＮｕからＮｂ-1
まで縮退させたノード９（４５）を作成する。ここで
は、上位２ビット目と３ビット目が縮退されるので、上
位２ビットと３ビットのみが”１”のアドレスH'60（０
１１０００００）をノード９（４５）のビットパタン情
報とし、アドレスパタン情報は、このH'60と追加ネット
ワークアドレスH'DFの論理積H'40（０１００００００）
をアドレスパタン情報とする。また、メモリアドレス０
には、”０”を入れ、メモリアドレス１には、次のノー
ドであるノード１０（４６）のメモリアドレスを入れ
る。そして、追加前のノード８（３３）の一つ手前のノ
ード（ノード１（３２、４４））のメモリアドレス１に
今作ったノード（ノード９（４５））のメモリアドレス
を入れる。そして、経路情報を作成し、ＮｌとＮｂとを
比較し、若し、等しく無ければ、Ｎｂ+1ビット目からＮ
ｌビット目までまとめた次のノードを作る。若し、Ｎｂ
とＮｌが等しい場合は、ノード１０（４６）に作成した
経路情報を接続する。この例では、等しくないので、５
ビットから８ビット目をまとめめた図１１のノード１１
（４８）を作成する。経路情報はこのノード１１（４
８）に接続し、さらに、ノード１０（４６）とノード１
１（４８）を接続するため、追加登録するネットワーク
アドレスH'DFの４ビット目を検査し、その値が”１”で
あるのでノード１０（４６）のメモリアドレス１に、ノ
ード１１（４８）のアドレスを入れる。さらに、分岐が
必要と判断されたノード８（４７）のアドレスをノード
１０（４６）のメモリアドレス０に入れ、ノード８（４
７）のビットパタン情報とアドレスパタン情報の上位Ｎ
ｕからＮｂビットまで（つまり２ビットから４ビットま
で）を”０”に変更して、H'DFの追加処理が終了する。

【００２１】最後に削除の一例について説明する。図１
２に削除のフローチャートを示す。この例では、図１１
のネットワークアドレスH'DFの経路情報の削除を行う方
法について述べる。先ず最初に、ネットワークアドレス
H'DFの経路情報が、登録されているかを調べる。経路情
報が登録されていなければ、未登録であるというエラー
を返す。この例では、ノード１１（４８）にその経路情
報５として接続されていることが検索できる。この検索
時に二つ前までのノードのメモリアドレスを保持してお
く。つまり、図１１のノード９（４５）とノード１０
（４６）のメモリアドレスを保持しておく。そして、一
つ前のノードつまり、ノード１０（４６）のメモリアド
レス１を”０”に変える。次に、経路情報５（４９）の
データとノード１１（４８）のデータをメモリから削除
する。削除の処理はこれで終了であるが、削除後に縮退
できるか否かを検査する。そこで、一つ手前のノード
（ノード１０（４６））の先程削除しなかった方のメモ
リアドレス（つまりメモリアドレス０）のノード（ノー
ド８（４７））と削除したノードの二つ手前のノード
（ノード９（４５））の分岐数をそれぞれ調べる。両ノ
ードとも二方向に分岐している場合は、縮退できないた
め正常終了で、削除処理を終了する。一つでも、一方向
が有れば、縮退できるので、縮退処理を行う。この例で
は、ノード８（４７）、ノード９（４５）ともに片方向
分岐であるので、ノード１０（４６）と一緒に縮退する
ことができる。縮退の方法は、先ず、縮退対象のノード
データのビットパタン情報の論理和を計算（H'7F) しそ
の値を縮退するノードの一番上流側のノードのビットパ
タン情報として格納する。そして、次に縮退しているノ
ードについてはアドレスパタン情報をそのまま使用し、
縮退していないノードについては、メモリアドレス０
が”０”の場合だけアドレスパタン情報をそのまま使用
し、そうでないときは、”０”をアドレスパタン情報と
して使用し、ビットパタン情報と同様に論理和を取る。
この例では、ノード９（４５）、ノード１０（４６）、
ノード８（４７）のアドレスパタン情報（H'40、H'10、
H'0D）の論理和（H'4D) をアドレスパタン情報とし、上
記で計算したH'7Fをビットパタン情報として、ノード９
（４５）に格納する。最後に、縮退する最下流のノード
のメモリアドレス０とメモリアドレス１をノード９（４
５）にコピーし、ノード８（４７）とノード１０（４
６）の領域を開放して終了となる。

【００２２】以上、キーとなるアドレスが８ビットの場
合について述べたが、３２ビット、６４ビットなどに拡
張した、データ蓄積方法、そのデータ蓄積方法によって
蓄積されたデータベース及びそのデータベースの検索
も、同じ処理で可能である。

【００２３】

【発明の効果】本発明を用いることにより、ネットワー
クアドレスに関連して蓄積されている経路情報や、電話
番号に関連して蓄積されている加入者データなどを比較
的少ない演算量で高速に検索することが可能となる。ま
た、追加及び削除も単純な処理の組み合わせで行うこと
が可能である。

【００２４】本発明は、特に、ローカルエリアネットワ
ーク中のルータやローカルエリアの交換機などで、ネッ
トワークアドレスや電話番号の一部が同じものが多く蓄
積されている場合に特に大きな効果を発揮する。

【図面の簡単な説明】

【図１】テーブル検索の例を説明するための図である。

【図２】従来の二分探索木の例を説明するための図であ
る。

【図３】複数ノードで連続して分岐の無い場合の例を説
明するための図である。

【図４】図３のH'835 のツリー部分を一つのノードに縮
退した図を説明するための模式図である。

【図５】検索アドレスのビット情報の表である。

【図６】本発明の一実施例の二分探索木を説明するため
の図である。

【図７】ノードの構成例を説明するための図である。

【図８】本発明の検索アルゴリズムの例を説明するため
の図である。

【図９】本発明の登録アルゴリズムの例を説明するため
の図（その１）である。

【図１０】本発明の登録アルゴリズムの例を説明するた
めの図（その２）である。

【図１１】本発明により登録を行った後の二分探索木の
例を説明するための図である。

【図１２】本発明の削除アルゴリズムの例を説明するた
めの図である。

【符号の説明】

１〜３０ 従来のノード ３１ 縮退ノード ３２〜３９、４４〜４８ 本発明のノード ４０〜４３、４９ 経路情報

Claims (6)

【特許請求の範囲】
1. 【請求項１】 数値化されたデータをキーにして二分探
   索木構造でデータを蓄積する方法において、 前記二分探索木のノードのうち分岐する先が一方向しか
   無いノードが複数連続するかどうかを判定し、連続する
   場合は、前記一連のノード群を一つのノードとし、該一
   連のノード群で検査すべきであったビット位置の全ての
   ビットを１にしそれ以外のビット位置のビットを０にし
   たデータをビットパタン情報として上記一つのノードに
   付加する段階と、前記数値化されたデータと該ビットパ
   タン情報のビットパタンとの論理積をとり、該論理積を
   そのノードのアドレスパタン情報として前記一つのノー
   ドに付加する段階とからなるデータ蓄積方法。
2. 【請求項２】 数値化されたデータをキーにして二分探
   索木構造でデータを蓄積する方法において、 前記二分探索木のノードのうち分岐する先が一方向しか
   無いノードが複数連続するかどうかを判定し、前記二分
   探索木のノードのうち分岐する先が一方向しか無いノー
   ドが複数連続しない場合は、そのノードで検査すべきビ
   ット位置のビットを１にしそれ以外のビット位置のビッ
   トを０にしたデータをビットパタン情報として上記ノー
   ドに付加する段階と、該ビットパタン情報をそのノード
   のアドレスパタン情報として前記ノードに付加する段階
   とからなるデータ蓄積方法。
3. 【請求項３】 数値化されたデータをキーにして二分探
   索木構造で蓄積されたデータベースにおいて、 前記二分探索木のノードのうち分岐する先が一方向しか
   無いノードが複数連続する場合は、前記一連のノード群
   を一つのノードとし、該一連のノード群で検査すべきで
   あったビット位置の全てのビットを１にしそれ以外のビ
   ット位置のビットを０にしたデータをビットパタン情報
   とし、前記数値化されたデータと該ビットパタン情報の
   ビットパタンとの論理積をとり、該論理積をそのノード
   のアドレスパタン情報としたノードからなる二分探索木
   構造で蓄積されたデータベース。
4. 【請求項４】 数値化されたデータをキーにして二分探
   索木構造で蓄積されたデータベースにおいて、 前記二分探索木のノードのうち分岐する先が一方向しか
   無いノードが複数連続しない場合は、そのノードで検査
   すべきビット位置のビットを１にしそれ以外のビット位
   置のビットを０にしたデータをビットパタン情報とし、
   該ビットパタン情報をそのノードのアドレスパタン情報
   としたノードからなる二分探索木構造で蓄積されたデー
   タベース。
5. 【請求項５】 二分探索木のノードのうち分岐する先が
   一方向しか無いノードが複数連続する場合は、この一連
   のノード群を一つのノードとし、該一連のノード群で検
   査すべきであったビット位置の全てのビットを１にしそ
   れ以外のビット位置のビットを０にしたデータをビット
   パタン情報とし、数値化されたデータベースの検索アド
   レス情報と該ビットパタン情報のビットパタンとの論理
   積をとり、該論理積をそのノードのアドレスパタン情報
   としたノードからなる二分探索木構造で蓄積されたデー
   タベースを検索する方法であって、 上記ノードに付加されている上記ビットパタン情報と検
   索キーとして示された数値化されたデータとの論理積を
   求める段階と、該論理積の値とアドレスパタン情報とを
   比較する段階と、その比較結果によって次のノ─ドを決
   定するか又は検索の終了かを決定する段階とからなるデ
   ータベースの検索方法。
6. 【請求項６】 数値化されたデータをキーにして二分探
   索木を用いて、該数値化されたデータと関連のある情報
   の検索方法において、 前記二分探索木のノードのうち分岐する先が一方向しか
   無いノードが複数連続しない場合は、そのノードで検査
   すべきビット位置のビットを１にしそれ以外のビット位
   置のビットを０にしたデータをビットパタン情報とし、
   該ビットパタン情報をそのノードのアドレスパタン情報
   としたノードからなる二分探索木構造で蓄積されたデー
   タベースを検索する方法であって、 上記ノードに付加されている上記ビットパタン情報と検
   索キーとして示された数値化されたデータとの論理積を
   とる段階と、該論理積の値とアドレスパタン情報とを比
   較する段階と、その比較結果によって次のノ─ドを決定
   するか又は検索の終了かを決定する段階とからなるデー
   タベースの検索方法。