JPH052607A - 木構造データ構造による高速探索方式 - Google Patents

Abstract

(57)【要約】 【目的】情報探索時の重複する無駄な比較を行わなくて
良く、且つ情報探索時の比較結果を有効に活用して高速
に情報探索を行えるデータ構造を構築することにより、
情報探索時の性能を向上させる。 【構成】探索を目的としたデータ構造において、データ
を識別するための識別子（キー）を複数登録する場合
に、それぞれのキーを比較しやすい大きさのブロックに
分割する。そして、キーの比較を先頭の方のブロックか
らブロック毎に行い、キーの先頭の方のブロックが等し
く、キーの後ろの方のブロックが異なる場合、等しい部
分のブロックを一つだけ保持し、異なる部分のブロック
を木構造のデータ構造になるようにポインタでつないで
保持する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データ構造に関し、特
に高速な情報の登録および探索が可能なデータ構造に関
するものである。

【０００２】

【従来の技術】従来より、情報の登録、探索を効率よく
実現するデータ構造として、ハッシングや木構造が用い
られている。ハッシングを用いたデータ構造では、発生
するデータ量の推定値が事前に分かっている場合、良好
な性能を得るデータ構造を作成することができる。しか
し、データ量が予測しにくく、またかなり変動する場
合、木構造の方が好ましいことが知られている。従来の
木構造のデータ構造には、２分木、ＡＶＬ木、最適木、
Ｂ木、２−３木、ＳＢＢ木等さまざまなものがあるが、
いずれも、木の枝の分かれ目や木の枝の先端（以下、節
点と記す）にキーを完全な形で持っていなければならな
い。非常に多くの場合、情報探索のキーは整数のように
一回の比較で大小の判定ができるものではなく、文字列
のように複数回に分割して比較しなければ大小の判定が
できないものである。しかし、従来の木構造ではポイン
タをたどり新しい節点に来る度にキーを先頭から比較し
直さなければならず、一回の比較で比較しきれないよう
なキーの比較回数の削減については全く考えられていな
い。また従来の木構造では、節点でのキーの比較で得ら
れる情報のうち、大きいか小さいかの二つの情報によっ
て、二つのポインタの中からどのポインタをたどるかを
決定しており、節点でのキーの比較で得られる情報の、
どこまでが等しくどこからが違うかという、より詳しい
情報を利用して、二つ以上のポインタの中から一つのポ
インタを選んでたどる方法については全く考えられてい
ない。

【０００３】なおこの種の技術として関連するものに
は、たとえばＡＮＳＩ（アメリカン・ナショナル・スタ
ンダード・フォ・インフォメーション・システムズ：Ａ
merican Ｎational Ｓtandard for information s
ystems）データベース・ランゲージ：database langua
ge−ＳＱＬ（規格番号Ｘ３．１３５−１９８６）などが
ある。

【０００４】

【発明が解決しようとする課題】木構造で各節点にそれ
ぞれのキーを完全な形で持つデータ構造では、木構造の
根（ｒｏｏｔ）から目的のキー又はキーの挿入場所を探
すときに、ポインタをたどり目的のキーにたどり着くま
での間の各節点で、その節点にあるキーと探しているキ
ーの比較を行う。キーは通常長いものもあれば短いもの
もある。そのため、節点にあるキーと探しているキーの
比較は一回で行えないものが多く、キーを分割し複数回
に分けて比較し、比較結果（キーの大小）によってどの
ポインタをたどるかを決定する場合がほとんどである。
そのため、キーの先頭の方は同じで後ろの方が違うキー
が複数登録されている場合（多くのキーを登録する場
合、必ずこのような状態が発生する）、これらの節点で
の比較で、毎回キーの先頭の同じ部分の比較をやりなお
さなければならないという問題が生じる。

【０００５】また、節点でのキーの比較でキーを複数の
ブロックに分割し、先頭の方のブロックから比較した場
合、得られる情報としては、どこまでのブロックは等し
いが、どこ以降のブロックが大きい又は小さい、という
情報が得られる。しかし、従来の木構造では、節点での
キーの比較結果によりポインタをたどるときにキーが大
きいか小さいかの情報しか利用しておらず、節点での比
較で得られる情報を十分に利用していないという問題が
ある。

【０００６】本発明の目的は、このような問題を解決
し、キーの先頭の方が同じで後ろの方が違うキーが有る
場合でも無駄な比較をできるだけ少なくし、また節点で
のキーの比較で得られる情報を十分に利用して、情報探
索の性能を向上させることが可能なデータ構造を提供す
ることにある。

【０００７】

【課題を解決するための手段】上記目的を達成するため
に、本発明のデータ構造（木構造）では、キーを複数登
録する場合に、それぞれのキーを比較しやすい大きさの
ブロックに分割し、キーの比較を先頭の方のブロックか
らブロック毎に行い、先頭の方のブロックが等しく後ろ
の方のブロックが異なる場合に、等しい部分のブロック
は一つだけ保持し、異なる部分以降のブロックを木構造
のデータ構造になるようにポインターでつないで保持す
ることに特徴がある。

【０００８】

【作用】本発明のデータ構造では、節点からポイントさ
れた先の節点には、ポイント元の節点にセットされてい
るキーと先頭の方から比較し、異なっている所より後ろ
の部分のブロックのみがセットされている。このため、
目的のキーと節点にセットされているキーの先頭の部分
が同じで後ろの部分が違う場合、その節点からポイント
された次の節点でのキーの比較では、前の節点でのキー
の比較で異なった部分が現れた所より後ろの比較のみを
行えば良い。このため、先頭の部分が同じで後ろの部分
が異なるキーが複数登録されている場合のキーの探索時
に各節点で無駄な比較を行わなくても良い。

【０００９】また、本発明のデータ構造では、節点に複
数のブロックを持ち、その各ブロック毎にポインタを持
っている。そして、キーの探索を行う場合、節点でキー
の比較を行い、どのブロックまでが等しくどのブロック
から異なるかにより、二つ以上のポインタの中からどの
ポインタをたどるかを決定できる。この結果、情報探索
の性能が向上する。

【００１０】

【実施例】以下、本発明の実施例を図面により詳細に説
明する。図１は、本発明の一実施例であるデータ構造に
７つのキーを登録したときのデータ構造の図である。図
２は、図１のデータ構造の節点の構成の詳細を示した図
である。図２において１は１つ以上の連続したブロック
をセットするエリアであり、２は各ブロック毎に持つポ
インタのエリアで、そのブロックより前のブロックは等
しいが、そのブロック以降のブロックが異なり、且つそ
のブロックの値よりも小さい値のブロックを持つキーを
示す節点へのポインタ（以下、左のポインタと記す）の
エリアである。３は各ブロック毎に持つポインタのエリ
アで、そのブロックより前のブロックは等しいが、その
ブロック以降のブロックが異なり、且つそのブロックの
値よりも大きい値のブロックを持つキーを示す節点への
ポインタ（以下、右のポインタと記す）のエリアであ
る。

【００１１】図１は、Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ、及びＧ
の７つのキーを登録した場合のデータ構造を示してい
る。４のｒｏｏｔは木構造の根の節点を示すポインタで
ある。Ａ［ｎ］は、キーＡのｎ番目のブロックを示し、
同様にＢ［ｎ］，Ｃ［ｎ］，…Ｇ［ｎ］はそれぞれのキ
ーのｎ番目のブロックを示す。ＮＩＬはキーの終端を示
すブロックである。ＮＩＬは可変長のキー登録を可能と
するために設けたものであり、固定長のキー登録のみを
行う場合ＮＩＬは必要ない。図１のデータ構造に登録さ
れているキーの長さ（ブロック数）を表１に示す。表２
にそれぞれのキーの大小関係を示す。

【００１２】

【表１】

【００１３】

【表２】

【００１４】まず、本データ構造へのキーの登録手順を
示しながら、本データ構造を説明する。キーがなにも登
録されていない状態では、木の根を示すｒｏｏｔ４には
０がセットされている。この状態でキーＡを登録する場
合、ｒｏｏｔ４に節点５のアドレスをセットし、節点５
にキーＡの全てのブロックをセットする。Ａ［５］のブ
ロックの後には、キーＡの終端を示すＮＩＬをセットし
ておく。

【００１５】次に、この状態にキーＢを登録する場合、
まずｒｏｏｔ４が指す節点５にセットされているキーＡ
と、これから登録するキーＢを先頭から比較する。キー
ＡとキーＢは、先頭のブロックから異なっており、Ａ
［１］よりＢ［１］の方が小さい。そこでＡ［１］の左
のポインタをチェックする。ポインタに何もセットされ
ていないので新しい節点６を作成し、節点６のアドレス
をＡ［１］の左のポインタにセットし、節点６にキーＢ
をセットする。

【００１６】次に、この状態にキーＣを登録する場合、
まずｒｏｏｔ４が指す節点５にセットされているキーＡ
と、これから登録するキーＣを先頭から比較する。キー
ＡとキーＣは、先頭のブロックから異なっており、Ａ
［１］よりＣ［１］の方が大きい。そこでＡ［１］の右
のポインタをチェックする。ポインタに何もセットされ
ていないので新しい節点７を作成し、節点７のアドレス
をＡ［１］の右のポインタにセットし、節点７にキーＣ
をセットする。

【００１７】つまり、キーＡ、キーＢ、及びキーＣは１
番目のブロックが異なるもの同志で２分木のデータ構造
を構成している。

【００１８】次に、この状態にキーＤを登録する場合、
まずｒｏｏｔ４が指す節点５にセットされているキーＡ
と、これから登録するキーＤを先頭から比較する。キー
ＡとキーＤは、１番目、２番目、及び３番目のブロック
は等しいが、４番目のブロックが異なりＡ［４］よりＤ
［４］の方が大きい。そこでＡ［４］の右のポインタを
チェックする。ポインタに何もセットされていないので
新しい節点８を作成し、節点８のアドレスをＡ［４］の
右のポインタにセットする。節点８にキーＤをセットす
るが、そのときにキーＡのブロックと等しいＤ［１］，
Ｄ［２］、及びＤ［３］はセットせずに、キーＡと異な
るＤ［４］以降のブロックのみをセットする。

【００１９】次に、この状態にキーＥを登録する場合、
まずｒｏｏｔ４が指す節点５にセットされているキーＡ
と、これから登録するキーＥを先頭から比較する。キー
ＡとキーＥは、１番目、２番目、及び３番目のブロック
は等しいが、４番目のブロックが異なりＡ［４］よりＥ
［４］の方が大きい。そこでＡ［４］の右のポインタを
チェックする。Ａ［４］の右のポインタはアドレスがセ
ットされているので、そのポインタが指す節点８にセッ
トされているキーＤとこれから登録するキーＥを比較す
る。ここで、Ａ［４］の右のポインタには、１番目から
３番目のブロックがキーＡと等しいキーのみしかセット
されていないので、節点８でのキーの比較では、１番目
から３番目のブロックの比較は不要である。Ｅ［４］と
Ｄ［４］を比較するとＤ［４］よりＥ［４］のほうが小
さい。そこでＤ［４］の左のポインタをチェックする。
ポインタに何もセットされていないので新しい節点９を
作成し、節点９のアドレスをＤ［４］の左のポインタに
セットする。節点９にキーＥをセットするが、そのとき
にキーＡ、及びキーＤのブロックと等しいＥ［１］，Ｅ
［２］、及びＥ［３］はセットせずに、キーＡ、及びキ
ーＤと異なるＥ［４］以降のブロックのみをセットす
る。

【００２０】つまり、本データ構造ではｎ番目までのブ
ロックが等しくｎ＋１番目以降のブロックが異なるキー
同志で２分木を構成する。また、このときにｎ番目まで
のブロックは１つだけ保持し、共有している。というこ
とに特長がある。

【００２１】次に、可変長のキー登録でのみ発生する特
殊なケースを説明する。Ａ，Ｂ，Ｃ，Ｄ、及びＥのキー
が登録されている状態にキーＦを登録する場合、まずｒ
ｏｏｔ４が指す節点５にセットされているキーＡと、こ
れから登録するキーＦを先頭から比較する。キーＡとキ
ーＦは、先頭のブロックから異なっており、Ａ［１］よ
りＦ［１］のほうが大きい。そこで、Ａ［１］の右のポ
インタをチェックする。Ａ［１］の右のポインタはアド
レスがセットされているので、そのポインタが指す節点
７にセットされているキーＣとこれから登録するキーＦ
を比較する。キーＣとキーＦは１番目、及び２番目のブ
ロックは等しいが、キーＣは２つのブロックしかなく、
キーＦは４つのブロックからなる。そこで、キーＣの終
端を示すブロックＮＩＬとＦ［３］を比較し、（ＮＩＬ
はいずれのブロックの値よりも小さい値をもつものとし
た場合）ＮＩＬよりもＦ［３］の方が大きいので、キー
Ｃの終端を示すＮＩＬの右のポインタをチェックする。
このＮＩＬの右のポインタに何もセットされていないの
で新しい節点１０を作成し、節点１０のアドレスをキー
Ｃの終端を示すＮＩＬの右のポインタにセットする。節
点１０にキーＦをセットするが、そのときにキーＣのブ
ロックと等しいＦ［１］、及びＦ［２］はセットせず
に、キーＣと異なるＦ［３］以降のブロックのみをセッ
トする。

【００２２】次に、上記の状態にキーＧをセットする場
合、まずｒｏｏｔ４が指す節点５にセットされているキ
ーＡと、これから登録するキーＧを先頭から比較する。
キーＡとキーＧは、先頭のブロックから異なっており、
Ａ［１］よりＧ［１］のほうが小さい。そこで、Ａ
［１］の左のポインタをチェックする。Ａ［１］の左の
ポインタはアドレスがセットされているので、そのポイ
ンタが指す節点６にセットされているキーＢと、これか
ら登録するキーＧを比較する。キーＢとキーＧは１番目
のブロックは等しいが、キーＢは４つのブロックがあ
り、キーＧは１つのブロックしかない。そこで、キーＧ
の終端を示すブロックＮＩＬとＢ［２］を比較し、Ｂ
［２］よりもＮＩＬの方が小さいので、Ｂ［２］の左の
ポインタをチェックする。このＢ［２］の左のポインタ
になにもセットされていないので新しい節点１１を作成
し、節点１１のアドレスをＢ［２］の左のポインタにセ
ットする。節点１１にキーＧをセットするが、そのとき
にキーＢのブロックと等しいＧ［１］はセットせずに、
キーＧの終端を示すＮＩＬのみをセットする。

【００２３】以上のように本データ構造では、キーの終
端を示すブロックＮＩＬを使用することにより可変長の
キーも登録することができる。また、ｎ番目までのブロ
ックが等しく、ｎ＋１番目以降のブロックが異なるキー
同志で２分木を構成しているので、目的のキーを探すと
きに重複している部分の無駄な比較が一切必要ない。更
に、２分木を構成するこれらのキーで、ｎ番目までのブ
ロックを共有し１つしか保持しないので、重複するデー
タを複数セットする必要がなく、データ構造を作成する
ときの時間が短縮される。

【００２４】本データ構造において、既に登録されてい
るキーの中から目的のキーを探索するときの手順は、前
に示したキーの登録のときに、新規の節点を追加する所
を探すときと同様の手順でポインタをたどることによ
り、目的のキーの探索が行える。この場合も、重複する
部分の無駄な比較がなく、キーの探索時間が短縮され
る。

【００２５】次に、本データ構造から、目的のキーを削
除するときの手順を説明する。キーを削除する場合、ま
ず前に示したキー探索の手順で削除するキーがセットさ
れている節点を探す。そして、その節点にセットされて
いるポインタの状態によってキーの削除手順が異なる。
まず、削除するキーがセットされている節点にポインタ
が１つもセットされていない場合の削除手順を示す。こ
の場合、削除するキーがセットされている節点を指して
いるポインタをクリアすれば良い。例えば、図１のデー
タ構造からキーＥを削除する場合、キーの探索を行い、
キーＥは節点９にセットされていることが分かる。節点
９は、節点８のＤ［４］の左のポインタから指されてい
るので、節点８のＤ［４］の左のポインタをクリアすれ
ば節点９がデータ構造から削除され、キーＥが削除でき
る。

【００２６】次に、削除するキーがセットされている節
点にポインタがセットされており、且つポインタがセッ
トされているブロックの内、最も後のブロック（以下、
このブロックを置き換え先頭ブロックと記す）のポイン
タが、左のポインタか右のポインタのいずれか一方しか
セットされていない場合の削除手順を示す。この場合、
削除するキーがセットされている節点の置き換え先頭ブ
ロック以降のブロック及びポインタに、置き換え先頭ブ
ロックの左のポインタ又は右のポインタが指す節点のブ
ロック及びポインタの内容を全て移せば良い。例えば、
図１のデータ構造からキーＡを削除する場合、キーの探
索を行い、キーＡは節点５にセットされていることが分
かる。節点５の中でポインタがセットされているブロッ
クは、Ａ［１］とＡ［４］だが、Ａ［４］の方が後のブ
ロックなのでＡ［４］が置き換え先頭ブロックとなる。
Ａ［４］のブロックには右のポインタしかなく、節点８
を指しているので、節点５のＡ［４］以降のブロック及
びポインタに節点８のブロック及びポインタの内容をコ
ピーする。そうすると図３の状態となる。Ａ［１］，Ａ
［２］、及びＡ［３］は、Ｄ［１］，Ｄ［２］、及びＤ
［３］と等しいから、節点５にセットされているキーは
ＡではなくＤとなり、このことからキーＡの削除が行わ
れていることが分かる。また、その他の登録状態は変わ
っていない。

【００２７】次に、削除するキーがセットされている節
点にポインタがセットされており、且つポインタがセッ
トされているブロックの内、最も後のブロック（置き換
え先頭ブロック）の左のポインタ及び右のポインタの両
方がセットされている場合の削除手順を示す。この場
合、まず削除するキーがセットされている節点の置き換
え先頭ブロックの右のポインタ（左のポインタをたどる
方法も考えられる）が指す節点を根（ｒｏｏｔ）とした
部分木構造を考える。この部分木構造で、各節点の先頭
のブロックの左のポインタだけをたどり、節点の先頭の
ブロックの左のポインタがセットされていない節点（以
下、置き換え元節点と記す）を探す。置き換え元節点が
見つかったら置き換え元節点を指しているポインタを、
置き換え元節点の先頭のブロックの右のポインタの内容
で置き換える。次に、削除するキーがセットされている
節点の置き換え先頭ブロック以降のブロックの内容を置
き換え元節点にセットされているブロックの内容で置き
換える。また削除するキーがセットされている節点の置
き換え先頭ブロックより１つ後のブロック以降のポイン
タを置き換え元節点の２番目以降のブロックのポインタ
で置き換えれば良い。例えば、図４のデータ構造からキ
ーＨを削除する場合、キーの探索を行い、キーＨは節点
１２にセットされていることが分かる。節点１２の中で
ポインタがセットされているブロックは、Ｈ［４］だけ
なのでＨ［４］が置き換え先頭ブロックとなる。Ｈ
［４］のブロックには右のポインタ及び左のポインタの
両方がセットされている。そこで、Ｈ［４］の右のポイ
ンタが指す節点１４を根（ｒｏｏｔ）とする部分木構造
で、各節点の先頭のブロックの左のポインタだけをたど
り、節点の先頭のブロックの左のポインタがセットされ
ていない節点（置き換え元節点）を探す。まず節点１４
の先頭のブロックの左のポインタにはアドレスがセット
されているのでポインタをたどり、次に節点１５をチェ
ックする。節点１５の先頭のブロックの左のポインタは
セットされていないので、節点１５が置き換え元節点と
なる。置き換え元節点が見つかったので置き換え元節点
を指している節点１４のＪ［４］の左のポインタを置き
換え元節点１５の先頭のブロックＫ［４］の右のポイン
タの内容で置き換える。次に、削除するキーがセットさ
れている節点１２の置き換え先頭ブロックＨ［４］以降
のブロックを、置き換え元節点１５にセットされている
ブロックの内容で置き換え、また削除するキーがセット
されている節点１２の置き換え先頭ブロックＨ［４］よ
り１つ後のブロック以降のポインタを置き換え元節点１
５の２番目以降のブロックのポインタで置き換える。す
ると図５の状態となる。Ｈ［１］，Ｈ［２］、及びＨ
［３］は、Ｋ［１］，Ｋ［２］、及びＫ［３］と等しい
はずであるから、節点１２にセットされているキーはＨ
ではなくキーＫとなり、このことからキーＨの削除が行
われていることが分かる。また、その他のキーの登録状
態は変わっていない。

【００２８】以上のように、本データ構造からのキーの
削除の手順は、２分木のデータ構造からキーを削除する
ときの手順と類似している。ただし、削除するキーがセ
ットされている節点を探索するときの手順は前に示した
ものが使用できるので、この場合も、重複する部分の無
駄な比較がなく、この分の時間が短縮できる。

【００２９】また、本データ構造は２分木の考えを使用
しており、各節点はより大きいものへのポインタ、又は
より小さいものへのポインタでつながれているので、本
データ構造に登録されたキーはおのずとソートされてい
ることは明らかである。

【００３０】このように、本実施例に示したデータ構造
においては、可変長のキーの登録、探索、削除、及びソ
ートを行うことができる。本実施例では、ｎ番目までの
ブロックが等しくｎ＋１番目以降のブロックが異なるキ
ー同志で通常の２分木を構成するものであるが、この他
にｎ番目までのブロックが等しくｎ＋１番目以降のブロ
ックが異なるキー同志でＡＶＬ木を構成する方法、最適
木を構成する方法、２−３木を構成する方法等さまざま
な方法が考えられるので、キー探索の最悪の場合の時間
を短縮する必要がある場合は、これらの方法を使用する
こともできる。

【００３１】

【発明の効果】以上説明したように、本発明によれば、
可変長のキーの登録、探索、削除、及びソートを行うこ
とができるデータ構造を作ることができる。このとき、
本データ構造ではキーの比較を先頭の方のブロックから
ブロック毎に行い、先頭の方のブロックが等しく後ろの
方のブロックが異なる場合に、等しい部分のブロックは
一つだけ保持し、異なる部分以降のブロックを木構造の
データ構造になるようにポインターでつないで保持して
いる。このため、目的のキーが登録されている節点、ま
たは目的のキーを追加する所を探索するときに、キーの
内容が重複する部分の無駄な比較がない。また、キーの
追加の場合は、キーの重複する部分のデータのセットは
１回だけでよい。更に、通常の２分木の場合、１つの節
点での比較により、 ・等しい ・大きい ・小さい の三つの情報しか得られない。このため、一つの節点で
の比較結果により、２つのポインタの中から１つのポイ
ンタを選んでたどることしかできない。しかし、本発明
の方式では、一つの節点での比較により、 ・等しい ・どこのブロックまで等しく、どこ以降のブロックが大
きい ・どこのブロックまで等しく、どこ以降のブロックが小
さい のように、より詳しい情報を得ることができる。このた
め、一つの節点での比較結果により、２つ以上のポイン
タの中から１つのポインタを選んでたどることができ
る。従って、目的のキーを探索し目的のキーがセットさ
れている節点にたどり着くまでに辿らなければならない
ポインタの数が削減される。そのため、従来の木構造の
データ構造でキーの登録、探索、削除、及びソートを実
施する場合より短い時間でこれらの機能を実現できる。
また、多くのキーを登録し、キーの重複する部分が多い
場合は、バイナリサーチと比較しても、より短い時間で
探索を実行することができる。

【図面の簡単な説明】

【図１】本発明の一実施例であるデータ構造にＡ，Ｂ，
Ｃ，Ｄ，Ｅ，Ｆ、及びＧの７つのキーを登録した場合の
データ構造を示す図である。

【図２】節点の構成を示す図である。

【図３】図１のデータ構造からキーＡを削除した後のデ
ータ構造を示す図である。

【図４】本発明の一実施例であるデータ構造にＨ，Ｉ，
Ｊ，Ｋ，Ｌ、及びＭの６つのキーを登録した場合のデー
タ構造を示す図である。

【図５】図４のデータ構造からキーＨを削除した後のデ
ータ構造を示す図である。

【符号の説明】

１…ブロックをセットするエリア、 ２…左のポインのタエリア、 ３…右のポインタのエリア、 ４…ｒｏｏｔポインタ、 ５〜１７…節点。

Claims (1)

1. 【特許請求の範囲】 【請求項１】探索を目的としたデータ構造において、デ
   ータを識別するための識別子（以下、キーと記す）を複
   数登録する場合に、それぞれのキーを一つ以上に分割し
   （分割したキーを以下、ブロックと記す）、キーの比較
   を先頭の方のブロックからブロック毎に行い、キーの先
   頭の方のブロックが等しくキーの後ろの方のブロックが
   異なる場合に、等しい部分のブロックは一つだけ保持
   し、異なる部分以降のブロックを木構造のデータ構造に
   なるようにポインターでつないで保持することを特徴と
   する木構造データ構造による高速探索方式。