(57)【要約】【課題】  ２分探索木構造を格納するデータ格納部におけるメモリ更新を簡単かつ短時間に行う。【解決手段】  データ格納部の総データ量が２n個であるとき、それぞれ２m個のメモリからなる複数個の一定サイズのメモリブロックを備え、前記木構造の段数をｋとするときに、【数１】2005117212.tif 000006である場合には、１段目からｋ段目までのデータを同一メモリブロックに格納し、ｋ＋１段目からは、ｋ＋１段目以上の各段のメモリを複数個のメモリブロックにそれぞれ分散して格納する。【選択図】  図１
2005117212.tif 000002
【特許請求の範囲】
【請求項１】
登録されたデータからキーワードに適合するデータを選び出すデータ検索装置において、
２分探索木構造を有するデータ格納部を備え、
当該データ格納部の総データ量が２n個であるとき、
それぞれ２m個のメモリからなる複数個の一定サイズのメモリブロックを備え、
前記木構造の段数をｋとするときに、
【数１】
2005117212.tif 000005
である場合には、１段目からｋ段目までのデータを同一メモリブロックに格納し、ｋ＋１段目からは、ｋ＋１段目以上の各段のメモリを複数個のメモリブロックにそれぞれ分散して格納する手段を備えた
ことを特徴とするデータ検索装置。
【請求項２】
それぞれ１段目からｋ段目までのデータを格納したメモリブロックをｋ個持つ請求項１記載のデータ検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２分探索による検索データを格納する記憶装置の構成方法に関する。
【背景技術】
【０００２】
従来は、ＩＰルータなどのパケット転送装置においては、パケットヘッダに搭載された宛先アドレスを元にルーティングテーブルを検索し、次ホップルータを決定している。ルーティングテーブルには宛先アドレスと次ホップルータの関係とを保持している。
【０００３】
このようなパケット転送装置では、入力されたパケットの宛先アドレスから２分探索のツリーを用いて次ホップルータを決定するという検索方法が広く用いられている。ツリーのノード上には宛先アドレスの境界値と次ホップルータを表す値とが格納されている。ツリーの検索はツリーのルート（頂点）から行い、各ノードではパケットの宛先アドレスとノードに格納されている境界値の大小の比較を行う。大小の比較によって次のノードへ順々に移っていく。ツリーの検索が終了した時点でパケットの宛先アドレスがどの範囲に入っているかを調査することで検索の回答結果となる次ホップルータが決定できる。
【０００４】
具体的な検索方法について図５を用いて説明する。検索すべきパケットの宛先アドレスが１．２．３．２０の場合、まずツリーのルート（ｒｏｏｔ：頂点）のノードで境界値と比較をする。この場合は、
１．２．３．２０＜１．２．３．２６
なので次ノードとして左下のノードへ移る。このノードでも境界値と比較する。
１．２．３．２０＞１．２．３．０
なので、今度は右下のノードへ移る。ここでも同様に比較を行うと
１．２．３．２０＜１．２．３．２５
であり、ここで検索を終了する。
【０００５】
パケットの宛先アドレスが含まれる範囲は、
１．２．３．０（ＮＨ＝Ｂ）＜１．２．３．２０＜１．２．３．２５（ＮＨ＝Ｃ）
となることがわかり、１．２．３．２０の次ホップルータはＢとなる。
【０００６】
ここで、注意すべきことは、ノードの境界値は「その境界値以上の場合、宛先アドレスの次ホップルータを表す値がそのノードが格納している次ホップルータを表す値となる」ということである。すなわち
１．２．３．０（ＮＨ＝Ｂ）≦Ｘ＜１．２．３．２５（ＮＨ＝Ｃ）
の場合、Ｘの次ホップルータはＣではなくＢである。したがって、「以上」で前ノードから１．２．３．２５（ＮＨ＝Ｃ）のノードに到着した場合、１．２．３．２５以外の値が宛先ＩＰアドレスであれば前ノード（ここでは１．２．３．０（ＮＨ＝Ｂ））に格納されている次ホップルータを表す値が解となる。
【０００７】
図６に具体的な検索例をもう１つ示す。今度はパケットの宛先アドレスが１．２．３．３０の場合である。図５と同様に検索を行うと、
１．２．３．２６（ＮＨ＝Ｂ）＜１．２．３．３０＜１．２．４．０（ＮＨ＝Ａ）
となることが分かり、パケットの宛先アドレス１．２．３０の次ホップルータはＢとなる。宛先アドレスが含まれる範囲を見つけるので、「未満」で前ノードから到着した場合には、１．２．４．０以外の値が宛先ＩＰアドレスであれば、前々ノードに格納されている次ホップルータを表す値が解となる（例えば特許文献１または２参照）。
【０００８】
【特許文献１】特開２０００−３３２７８６号公報
【特許文献２】特開２０００−３５８０６４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従来、２分探索木を格納するデータ格納部は、図４のようなメモリ構成をとっていた。この構成の場合、メモリ量は最小となるが、データ更新を行う場合、データを追加する場合、データを削除する場合、共に２分探索のデータが大幅に変更されてしまう。例えば、追加または削除の場合には、いずれかのメモリに追加または削除を行う度に、全てのメモリ内容を１つずつずらして更新する必要がある。
【００１０】
本発明は、このような背景に行われたものであって、２分探索木構造を格納するデータ格納部におけるメモリ更新を簡単かつ短時間に行うことができるデータ検索装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、登録されたデータからキーワードに適合するデータを選び出すデータ検索装置であって、２分探索木構造を有するデータ格納部を備え、当該データ格納部の総データ量が２n個であるとき、それぞれ２m個のメモリからなる複数個の一定サイズのメモリブロックを備え、前記木構造の段数をｋとするときに、
【数１】
2005117212.tif 000003
である場合には、１段目からｋ段目までのデータを同一メモリブロックに格納し、ｋ＋１段目からは、ｋ＋１段目以上の各段のメモリを複数個のメモリブロックにそれぞれ分散して格納する手段を備えたことを特徴とする。
【００１２】
これにより、データ追加に備えた空きメモリを用意しておくことができるため、２分木探索構造におけるメモリ更新を簡単かつ短時間に行うことができる。
【００１３】
また、それぞれ１段目からｋ段目までのデータを格納したメモリブロックをｋ個持つこともできる。これによれば、メモリ量は多くなるが、各検索段毎に並列にメモリにアクセスできるため、トータルの検索時間を短くすることができる。あるいは、データ更新に際し、デュプリケートしてデータを持っているため、１つのデータを更新している間にも、検索を行うことができる。
【発明の効果】
【００１４】
本発明により、データ更新を行う際に、メモリのブロック化により、メモリブロック内のデータ更新、メモリブロック間のデータ更新と、更新手順を分けることが可能となり、ブロック内のデータ更新の場合には、更新対象メモリブロック内だけの更新であり、対象外のメモリブロックには影響がなく、更新時間を短くすることができる。また、ブロック間のデータ更新に関しても、複数の対象ブロックだけにしか影響がなく、更新が容易となる。
【発明を実施するための最良の形態】
【００１５】
（実施例１）
図１は、登録されたデータからキーワードに適合するデータを選び出すデータ検索装置の構造である。データ格納部（記憶装置）１と、データ検索論理部２と、データ更新部３とからなる。データ格納部１は、キーワードと検索対象データを格納したメモリ（記憶装置）であり、データ検索論理部２は、２分探索を行う演算部である。データ更新部３は、検索データを更新するための機能である。
【００１６】
図４は、２分探索木を格納する従来のデータ格納部の構造である。２分探索法は、検索段数ｉに必要なデータ量が２i-1のオーダーである。そのため、段数によって必要なメモリ量が大きくなってしまう。
【００１７】
図２は第一の実施例を示した図であり、メモリブロックサイズを１６と３２にした２例を示している。従来のデータ格納部と本実施例のデータ格納部１とのメモリ構成の比較のため、対応関係を示す丸付き数字を付した。メモリブロックサイズが１６の場合でも３２の場合でも、どちらの構成も空きメモリは１であり、メモリを効率よく実装している。このように、本発明に従ったメモリ構成を用いることにより、空きメモリを小さくすることが可能である。
【００１８】
すなわち、データ格納部１の総データ量は、２分探索木構造が６段であることから、２5＝３２個である。このとき、それぞれ２４＝１６個のメモリからなる複数個の一定サイズのメモリブロックを備え、２分探索木構造の段数を６とするときに、
【数２】
2005117212.tif 000004
が１６以下となるｋを求めると、ｋ＝４である。したがって、１段目から３段目までのデータを同一メモリブロックに格納し、４段目からは、４段目以上の各段のメモリを複数個のメモリブロックにそれぞれ分散して格納する（請求項１）。
【００１９】
また、他の例として、データ格納部１の総データ量は、２分探索木構造が６段であることから、２5＝３２個である。このとき、それぞれ２５＝３２個のメモリからなる複数個の一定サイズのメモリブロックを備え、２分探索木構造の段数を６とするときに、
［数２］
が３２以下となるｋを求めると、ｋ＝５である。したがって、１段目から５段目までのデータを同一メモリブロックに格納し、６段目からは、６段目以上の各段のメモリを複数個のメモリブロックにそれぞれ分散して格納する（請求項１）。
【００２０】
これにより、どちらの構成も空きメモリは１であり、メモリを効率よく実装している。本発明に従ったメモリ構成を用いることにより、空きメモリを小さくすることが可能である。
【００２１】
（実施例２）
図３は第二の実施例である。第二実施例では、それぞれ１段目からｋ段目までのデータを格納したメモリブロックをｋ個持つ（請求項２）。すなわち、第一の実施例で、１つのメモリブロックに収められたデータを検索段毎に同じデータを持たせた構成になっている。この方法は、１．メモリ量は多くなるが、各検索段毎に並列にメモリにアクセスできるため、トータルの検索時間を短くする効果が得られる。２．データ更新に際し、デュプリケートしてデータを持っているため、１つのデータを更新している間にも、検索を行うことができる。
【産業上の利用可能性】
【００２２】
本発明により、データの更新時間を短くすることができる。また、ブロック間のデータ更新に関しても、複数の対象ブロックだけにしか影響がなく、更新が容易となる。これにより、大規模な２分探索木を用いたデータ検索装置を構成した場合に、データ更新を簡単化することができるため、ユーザの利便性を向上させることができる。
【図面の簡単な説明】
【００２３】
【図１】本実施形態のデータ検索装置の構成図。
【図２】第一実施形態のデータ格納部の構成図。
【図３】第二実施形態のデータ格納部の構成図。
【図４】２分探索木を格納する従来のデータ格納部の構成図。
【図５】２分探索手順を説明するための図。
【図６】２分探索手順を説明するための図。
【符号の説明】
【００２４】
１  データ格納部
２  データ検索論理部
３  データ更新部
【図１】
2005117212.tif 000007
【図２】
2005117212.tif 000008
【図３】
2005117212.tif 000009
【図４】
2005117212.tif 000010
【図５】
2005117212.tif 000011
【図６】
2005117212.tif 000012