(57)【特許請求の範囲】
【請求項１】
メモリデータがデータユニットとして記憶され、各データユニットに対して専用の記憶スペースが指定される機能的メモリを実施するための方法であって、
上記メモリは、多数の異なるレベルにノードを有するツリー形状のハイアラーキーを含むディレクトリ構造として実施され、少なくとも幾つかのノードは、エレメントテーブルの個々のエレメントがツリー形状ハイアラーキーにおいて下位ノードを指すポインタを含みそしてエレメントテーブルの個々のエレメントが空でもあるようなエレメントテーブルにノードが関連付けされるようなものであり、上記エレメントの内容が空である場合にエレメントの内容はゼロポインタに対応し、上記エレメントテーブルにおけるエレメントの数は２の累乗に対応し、
上記ディレクトリ構造で実施されるアドレス計算は、次の段階より成り、即ち
（ａ）ツリー形状ハイアラーキーの最上位レベルのノードにおいて、使用するサーチキーによって形成されたビットストリングから所与の数のビットを選択し、その選択されたビットから、ノードにおいて次のノードのアドレスをシークするところのサーチワードを形成し、そして上記ノードへ進み、
（ｂ）使用するサーチキーによって形成されたビットストリングにおいて選択されなかったビットから所定数のビットを選択し、そしてその選択されたビットから、アクセスされたノードにおいて下位レベルの更に別の新たなノードのアドレスをシークするところのサーチワードを形成し、
そしてゼロポインタを含むエレメントに遭遇するまで又は最下位レベルのノードがアクセスされるまで上記段階（ｂ）を繰り返し、
データユニットが構造体に追加されるときには、上記アドレス計算によってデータユニットを検索できるところのポインタがノードに追加され、
更に、ディレクトリ構造体において、第１の数のエレメントをエレメントテーブルが含むところのノードにポインタが先ず追加され、これらノードは、非ゼロポインタの物理的記憶位置を示すビットパターンとともに、非ゼロポインタが物理的に記憶される巾圧縮されたノードであり、上記方法は、
ノードにおけるポインタの数が、上記第１の数より小さい所定のスレッシュホールド値に対応するまで、個々の巾圧縮されたノードを指すポインタの追加を許し、そして
巾圧縮されたノードに受け入れられるポインタの数が上記スレッシュホールド値を越えるや否や、巾圧縮されたノードを、親ノード及び個別の子ノードにより構成されたノードのクラスターに変換する、
という段階を含むことを特徴とする方法。
【請求項２】
上記第１の数は１６であり、巾圧縮されたノードを指すポインタの追加は、その追加後のノードにおけるポインタの数が１３以下であるたびに許され、そして巾圧縮されたノードは、巾圧縮されたノードに受け入れられるポインタの数が値１３を越えるたびに巾圧縮された４−エレメント・ノードのクラスターに変換される請求項１に記載の方法。
【請求項３】
上記構造体の全てのノードが巾圧縮されたノードである請求項１に記載の方法。
【請求項４】
上記親ノード及び子ノードにより形成されるノードのクラスターは、親ノードの孫ノードの数が上記スレッシュホールド値以下に減少するや否や単一の巾圧縮されたノードに再変換される請求項１又は２に記載の方法。
【請求項５】
非ゼロポインタは、上記エレメントテーブルにおけるのと同じ順序で次々に巾圧縮されたノードに記憶される請求項１に記載の方法。
【請求項６】
上記ビットパターンは、テーブル内のエレメントごとに１ビットを含み、各ビットは、対応するエレメントがゼロポインタを有するか非ゼロポインタを有するかを指示する請求項５に記載の方法。
【請求項７】
データユニットを記憶するためのデータ構造を有するデータを記録したコンピュータ読み取り可能な記録媒体であって、上記データ構造においては、各々の場合に使用されるサーチキーにより構成されるビットストリングから作られるサーチワードを使用することにより進行がなされ、上記データ構造は、多数の異なるハイアラーキーレベルにノードを有するツリー形状のハイアラーキーを含み、少なくとも幾つかのノードは、エレメントテーブルの個々のエレメントがツリー形状ハイアラーキーにおいて下位ノードを指すポインタを含みそしてエレメントテーブルの個々のエレメントが空でもあるようなエレメントテーブルにノードが関連付けされるようなものであり、エレメントテーブルの個々のエレメントが空である場合にエレメントの内容はゼロポインタに対応し、上記エレメントテーブルにおけるエレメントの数は２の累乗に対応し、上記ディレクトリ構造体における少なくとも幾つかのノードは、非ゼロポインタの物理的記憶位置を示すビットパターン(BP1)とともに、非ゼロポインタのみが物理的に記憶された巾圧縮されたノードが含まれる、データ構造を有するデータを記録したコンピュータ読み取り可能な記録媒体において、
上記ノードの第１部分は、ノードに記憶されるポインタの数が、常に、ノードのエレメントテーブルにおけるエレメントの数より小さい所定のスレッシュホールド値以下であるようなものであり、そして
上記ノードの第２部分は、親ノード及びそれより低いハイアラーキーレベルにある子ノードで各々構成されたノードのクラスターによって構成され、上記親ノードの孫ノードの数は、常に、上記スレッシュホールド値を越えるものであり、
上記データ構造は、巾圧縮されたノードに受け入れられるポインタの数が上記スレッシュホールド値を越えるや否や、巾圧縮されたノードを、上記ノードのクラスターに変換することを含む処理によって得られることを特徴とするデータ構造を有するデータを記録したコンピュータ読み取り可能な記録媒体。
【請求項８】
少なくとも上記第１部分のノードは、巾圧縮されたノードである請求項７に記載のデータ構造を有するデータを記録したコンピュータ読み取り可能な記録媒体。
【請求項９】
第１部分及び第２部分の両方におけるノードが巾圧縮される請求項７に記載のデータ構造を有するデータを記録したコンピュータ読み取り可能な記録媒体。
【請求項１０】
上記データ構造体における実質的に全てのノードが巾圧縮されたノードである請求項７に記載のデータ構造を有するデータを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【技術分野】
本発明は、一般に、メモリの実施に係る。より詳細には、本発明は、機能的デジタルトリー(trie)構造をベースとする全てのメモリに関連して使用されることが意図される。しかしながら、この解決策は、主として中央メモリデータベースに意図される。機能的構造とは、追加のような更新が、ルートから追加ポイントまでの経路を先ずコピーしそしてそのコピーされたデータに対して追加を行うようにして（追加は既存のデータに直接的に行われない）実行されるメモリを指す。このような更新手順は、「コピー・オン・ライト(copy-on-write)」とも称される。
【０００２】
【背景技術】
デジタルトリー（トリー(trie)という語は、英語の「検索(retrieval)」から生じたものである）と称される公知の一次元ディレクトリ構造は、本発明の原理の基礎をなすものである。デジタルトリー構造は、バケットトリー及びバケットをもたないトリーの２つの形式で実施することができる。
バケットデジタルトリー構造とは、バケット及びトリーノードの２つの形式のノードで構成されたツリー形状の構造体である。バケットとは、多数のデータユニット、又はデータユニットを指す多数のポインタ、或いは多数のサーチキー／データユニット対、又は多数のサーチキー／ポインタ対を受け入れることのできるデータ構造体である。上記の数として１より大きな最大サイズが定義されている。しかしながら、バケットは、上記最大数より少数のデータユニット、ポインタ又はキー／ポインタ対を含むことができ、この場合に、バケットはいっぱいではない。一方、トリーは、検索をガイドするアレーで、２のｋ乗（２k）個のエレメントというサイズを有する。トリーノードに１つのエレメントが使用される場合には、それがディレクトリツリーの次のレベルにおけるトリーノードを指すか、又はバケットを指す。他の場合には、エレメントがフリー（空）である。
【０００３】
データベースにおけるサーチは、一度にｋビットづつ、サーチキー（これは、例えば、移動電話ネットワーク又は電話交換機の加入者データベースの場合に、通常、加入者の電話番号に対応する２進数である）を検査することにより行われる。サーチされるべきビットは、構造体のルートレベル（第１トリーノード）において最も左のｋビットがサーチされ、構造体の第２レベルにおいてそれら最も左のビットの次のｋビットがサーチされ、というように選択される。サーチされるべきビットは、トリーノードに含まれたエレメントテーブルをインデックスするために直接使用される無符号の２進整数として解釈され、そのインデックスは、テーブル内の所与のエレメントを指示する。インデックスで指示されたエレメントがフリーである場合には、サーチが不成功で終了する。エレメントが次のレベルのトリーノードを指す場合には、サーチキーから抽出されたｋ個の次のビットが上述したようにそのレベルにおいてサーチされる。比較の結果として、ルーチンは、トリーノードにおいて次のレベルのトリーノード又はバケットへ分岐する。エレメントが、キーを含むバケットを挿す場合には、そこに記憶されたキーがサーチキーと比較される。従って、サーチがバケットに遭遇した後でなければ全サーチキーが比較されない。キーが等しい場合には、サーチが成功であり、バケットのポインタで指示された記憶アドレスにおいて所望のデータユニットが得られる。キーが異なる場合には、サーチが不成功で終了する。
【０００４】
バケットレスのトリー構造は、バケットをもたず、データユニット、データユニットを指すポインタ、サーチキー／データユニット対、又はサーチキー／ポインタ対である１つのエレメントのみを含むリーフノードがバケットに対応する。ここに示す説明では、バケットレストリー構造体におけるリーフノードより上のノードは、内部ノードと称され、これらは、バケット構造体におけるトリーノードに対応する（即ち、それらは、トリーノードとして同様のテーブルを含む）。従って、バケットレスデジタルトリー構造では、ノードが内部ノード又はリーフノードのいずれかである。バケットにより、ディレクトリ構造を再編成する必要性を延期することができる。というのは、このような必要性が生じるときまでに非常に多数のポインタ、データユニット、サーチキー／データユニット対、又はサーチキー／ポインタ対を受け入れることができるからである。
【０００５】
図１は、キーが４ビットの長さを有しそしてｋ＝２であり、従って、各トリーノードが２2＝４エレメントを有し、そしてキーから抽出された２つのビットが各レベルにおいてサーチされるようなデジタルトリー構造体の一例を示す。リーフは、参照文字Ａ、Ｂ、Ｃ、Ｄ、・・Ｈ、・・Ｍ、Ｎ、Ｏ及びＰで示されている。従って、リーフは、ツリーにおいて下位レベルを指さないノードである。図１において、内部ノードは、参照文字ＩＮ１、・・ＩＮ５で示され、そして内部ノードのエレメントは、参照文字ＮＥで示されている。
図１に例示するケースでは、図示されたリーフに対するサーチキーがＡ＝００００、Ｂ＝０００１、Ｃ＝００１０、・・Ｈ＝０１１１、・・及びＰ＝１１１１である。このケースでは、実際のデータ、例えば、当該加入者の電話番号及びその加入者に関連した他の情報が見出されるところのデータベースＳＤの記憶位置を指すポインタが各リーフに記憶される。実際の加入者データは、例えば、図示された形式の逐次ファイルとしてデータベースに記憶されてもよい。サーチは、例えば、記録Ｈのサーチキーに基づき、最初にサーチキーから２つの最も左のビット（０１）を抽出しそしてそれらを解釈することによって実行され、これは、ノードＩＮ１の第２エレメントを与え、これは次のレベルにおけるノードＩＮ３を指すポインタを含む。このレベルでは、２つの次のビット（１１）がサーチキーから抽出され、従って、そのノードの第４エレメントを形成し、これは記録Ｈを指す。
【０００６】
ポインタに代わって、リーフは、実際のデータファイル（より一般的な用語でデータユニットとも称される）を含んでもよい（サーチキーに加えて）。従って、例えば、加入者Ａに関するデータ（図１）は、リーフＡに配置され、加入者Ｂに関するデータは、リーフＢに配置され、等々となる。
本発明は、主に、バケットレスのトリー構造体に係る。というのは、本発明による解決策がバケット構造体と同じ効果を与え、ひいては、本発明は、バケットレス構造体において大きな利益をもたらすからである。これらのことは、以下に詳細に説明する。
又、サーチキーは、多次元であってもよい。換言すれば、サーチキーは、多数の属性（例えば、加入者の姓及び１つ以上の名）を含んでもよい。このような多次元トリー構造が国際出願ＰＣＴ／ＦＩ９５／００３１９号（公告番号ＷＯ９５／３４１５５号）に開示されている。上記構造において、一度に所定数のビットが各次元から他の次元に関わりなく選択されるようにしてアドレス計算が実行される。ここで、トリー構造の個々のノードにおいて、各次元でサーチされるべきサーチキービットの数を予め決定することにより、各次元に対して他の次元に関わりなく固定限界が設定される。このような構造では、サーチキーの値の分布が前もって分かるときにメモリ回路要求を拘束することができ、この場合に、静的な形態で構造を実施することができる。
【０００７】
現在キー分布に基づき構造を効率及び記憶スペース占有度に関して最適なものに再編成する可能性が望まれる場合には、キー分布が変化するときにノードのサイズが動的に変化しなければならない。キー分布が均一であるときには、ノードのサイズを増加して構造体をより平坦にすることができる（平坦な構造は高速な検索を伴う）。他方、キー分布が非均一で、それに関連して記憶スペース占有度が、動的なノードサイズを使用するメモリ構造に問題を生じる状態では、ノードサイズを小さく維持することができ、これは、ローカル位置で更に均一なキー分布を可能にし、従って、記憶スペース占有度を小さくする。ノードサイズを動的に変更するには、デジタルトリー構造により構成されたツリー型ハイアラーキーの各ノードにおいて、使用するサーチキーで構成されたビットストリングからノード特有のビット数が選択されるように、アドレス計算を実行する必要がある。ノードを動的に再編成するには、当然、処理容量の一部分を必要とする。
【０００８】
固定ノードサイズと、動的に変化するノードサイズとの間の選択は、例えば、メモリがどんな形式のアプリケーションに意図されるか、データベースサーチ、追加及び削除の回数及びそれらオペレーションの割合に依存する。
従って、メモリの効率及び性能は、とりわけ、トリー構造に必要な記憶スペース及びトリー構造の深さによって左右される。ルートから更新ポイントまでの全サーチ経路が更新に関連してコピーされねばならない機能的デジタルトリー構造では、メモリの性能は、このような経路がどれほど多くのコピーされるべきワードを含むかによっても左右される。従って、メモリにおいて圧縮が行われる場合には、コピーされるべきデータの量が、圧縮の結果として、メモリの性能を損なう程度まで増加しないようにして、これを行わねばならない。
【０００９】
米国特許第５，２７６，８６８号は、トリーノードの圧縮方法について開示している。このシステムは、２つのノードサイズ、即ちクオド及びサイズ１６のノードしかサポートしない。この方法において、幾つかのゼロポインタがノードから除去され、５未満の非ゼロポインタを有するノードが圧縮クオドに変換され、一方、残りのノードが非圧縮状態に維持される。従って、この構造体は、圧縮ノード及びサイズ１６の非圧縮ノードの両方を含む。構造体には依然としてゼロポインタを記憶しなければならないので、構造体は、記憶スペース要件及びコピーコストに観点で非常に良好な結果を与えない。又、２つのノードサイズしか可能でないので、この構造体は、一度に１つのワードを使用するようにメモリを割り当てることのできる効率的なメモリ管理機能をもつ機能的メモリ又は他のメモリには充分適していない。
従って、機能的トリー構造に伴う問題は、全ての上記ファクタを考慮してメモリ性能をできるだけ良好にするために構造体においていかに圧縮を行わねばならないかである。
【００１０】
【発明の開示】
そこで、本発明の目的は、上記問題の解決策を提供することである。この目的は、独立請求項に記載した方法によって達成される。
本発明は、例えば、上記米国特許において参照がなされている公知の巾圧縮を使用するものである。このため、トリーツリーのノードサイズは、最初にできるだけ大きく予め選択され、即ち構造体に使用されるノードの論理的サイズは、好ましくは１６であるが、原理的にはもっと大きくてもよい。本発明によれば、巾圧縮ノードを増加することは最大限界まで許され、これは、ノードの最大サイズより小さい。ノードは、このスレッシュホールド値を越えるように成長するや否やノードのクラスターに分割される。例えば、１６エレメントを有する巾圧縮されたノードの場合には、１３個の子ノードをスレッシュホールド値として使用するのが好ましい。子ノードの数が１３を越えた場合には、親ノードが、圧縮されたクオドノードのクラスターへ分解される。
【００１１】
本発明による考え方は、巾圧縮されたノードのサイズが増加するにつれて、コピーコストがある段階で急激に増加するという洞察をベースとしている。というのは、更新に関連して実行されるコピーが常にツリーのルート（根）から更新ポイントまで行われ、そして各コピー周期にコピーされるツリーの上部におけるノードが最初に充填されそして通常は下位ノードよりいっぱいになるからである。ここで、巾圧縮されたノードの充填レートを高めることは、ある段階に達したときには無益であり、コピーコストの増加が、巾圧縮で得られる効果を完全に排除する。本発明によれば、遅くともこの段階において、巾圧縮されたノードが２つの異なるハイアラーキーレベルにおいてノードのクラスターに変換されて戻される。
【００１２】
又、本発明の考え方は、コピーコストのこのような急激な増加を回避し、形成されるべきノードのクラスターを上記要件に関してできるだけ効果的なものにすることである。例えば、上述したスレッシュホールド値１３は、コピーコストがまだ急激に増加し得ないという意味で、サイズ１６のノードに対して効果的であり、他方、サイズが１３より大きいときには、クオドノードのクラスターを形成するとき親ノードがゼロポインタを含まないことが確実である。従って、サーチオペレーションを加速することができる。というのは、上記ノードにおけるポイントの数をサーチに関連して検査する必要がないからである。更に、形成されるべきノードクラスターにおいては、そのクラスターにおける子ノードはいずれも経路圧縮されないことが確実である（構造体では経路圧縮を使用するのが好ましい）。というのは、この場合に、親ノードがいっぱいでありそして各子ノードが少なくとも２つの子ノードを有するからである（クオドクラスターにおいて実行されるべき経路圧縮は計算を遅らせる）。
【００１３】
メモリ性能を全時間にわたって最適に保つために、クラスターの親ノードの孫ノードの数が上記スレッシュホールド以下に下がったときにノードのクラスターを巾圧縮ノードに再組み立てするのが好ましい。
本発明による解決策を使用するときには、更新に関連してコピーされるワードの数を実質的に増加せずに、ひいては、巾圧縮によって得られる効果を減少せずに、機能的構造体のメモリ消費を巾圧縮によって減少することができる。
以下、図２ないし１１の例を参照して本発明の好ましい実施形態を詳細に説明する。
【００１４】
【発明を実施するための最良の形態】
機能的トリー構造体のノードに巾圧縮が使用されるときには、構造体に対して大きなノードサイズを選択することによりそれを効率的に利用することができる。従って、本発明による構造体では、スタートポイントが、クオドより明らかに大きいノードサイズ、好ましくは（論理的）サイズ１６のノードである。図２はこのようなノードＮ２０を示し、これは、ここに例示するケースでは、ツリーにおいて下方を指す４つの非ゼロポインタを有する。構造体のノードにおいてゼロとは異なるポインタのみを記憶することにより公知の巾圧縮が実行される。非ゼロポインタに加えて、ビットパターン即ちチャートＢＰ１がノードに関連して記憶され、それに基づいて、ノードのエレメントテーブルの論理的インデックスに対応するポインタがゼロポインタであるかどうか決定することができ、そしてもしそうでなければ、上記論理的インデックスに対応するポインタがノードに物理的に配置される。圧縮が使用されるときには、ノードの標準長さエレメントテーブル（１６エレメント）がビットパターンにより物理的記憶位置のテーブルとして表わされ、その長さは、各々の場合にノードがどれほど多くのゼロポインタを含むかに基づいて変化する。それ故、巾圧縮に関連して、ノードの論理的サイズ（即ちエレメントテーブルのサイズ）は変化せず、ノードの物理的サイズが減少することに注意されたい。というのは、圧縮ノードでは、ゼロポインタが記憶スペースを占有しないからである。その結果、全て非ゼロポインタが続く図３の巾圧縮ノードＮ３０が図２のノードから得られる。このノードは、４つの物理的エレメント（ポインタＡ、・・Ｄ）しか含まず、更に、ビットパターンＢＰ１がノードに記憶され、これは、サーチキーから形成されるエレメントテーブルインデックスに対応するポインタの物理的位置を指示する。ここに例示するケースでは、ビットパターンは、エレメントテーブルの各エレメント（論理的インデックス）に対して１ビットを有し、そして各ビットは、それに対応するエレメントが非ゼロポインタを含むかゼロポインタを含むかを指示する。図示された例示的ケースでは、１は非ゼロポインタを示し、そして０はゼロポインタを示す。ポインタは、順序を保持するように圧縮ノードに記憶される（そしてゼロポインタに対してはスペースが指定されない）ので、図３の圧縮ノードの場合には、ゼロポインタがエレメントテーブルインデックス０に対応し、非ゼロポインタがエレメントテーブルインデックス１に対応し、その物理的インデックスは０であり、ゼロポインタがエレメントテーブルインデックス２、・・６に対応し、非ゼロポインタがエレメントテーブルインデックス７及び８に対応し、それらの物理的インデックスは１及び２であり、ゼロポインタがエレメントテーブルインデックス９、・・１２に対応し、非ゼロポインタがエレメントテーブルインデックス１３に対応し、その物理的インデックスは３であり、そしてゼロポインタがエレメントテーブルインデックス１４及び１５に対応することが分かる。従って、サーチキービットから形成される論理的インデックスに対応するポインタがノード内に見出される。圧縮ノードのビットパターンがエレメントテーブルの各エレメント（論理的インデックス）に対して１ビットを有するような圧縮方法は、それ自体知られている。このような解決策は、例えば、上記米国特許第５，２７６，８６８号に示されている。
【００１５】
圧縮ノードに対するアドレス計算は、（論理的）エレメントテーブルインデックスが、サーチキーから抽出されたビットから通常のやり方で最初に形成されるようにして実行される。その後に、このインデックスに対応するビットがビットパターンから読み出される。このビットが、ゼロポインタに関与することを指示する場合には、サーチが不成功で終了する。このビットが、非ゼロポインタに関与することを指示する場合には、上記エレメントテーブルインデックスに対応するポインタの物理的な位置（物理的インデックス）がビットパターンにより決定される。エレメントテーブルの各インデックスに対して１ビットを有する図３に示す種類のビットパターンが使用されるときには、ビットパターンの始めから、エレメントテーブルインデックスに対応するビットまで１ビットの数をカウントすることにより、物理的なインデックスが直接得られる。
別の形態は、論理的インデックスに対応するビットパターンのビットが０であるかどうかチェックせずにサーチを続けることであり、即ちこのチェックを行わずに物理的インデックスを検索することができる。この場合には、サーチがリーフまで続けられ、そこで、キー比較が実行される。リーフにおける上記比較に基づいてサーチ欠陥が検出される。
【００１６】
しかしながら、ビットパターンに使用されるビットの数は、論理的インデックスの数から変動することがあり、そしてビットパターンは、種々のコード化方法を使用することができ、これにより、論理的インデックスに対応する物理的記憶位置が見つかる。更に、上述した解決策は、短いビットパターン及び簡単なコードメカニズムを可能にする。
上述したように、本発明による解決策は、巾圧縮ノードのサイズが増加するときに、コピーコストがある段階で急激に増加して、ノードの充填レートを高めることが無益となり、コピーコストの増加が、巾圧縮の増加で得られる効果を完全に排除するという洞察に基づくものである。トリーツリーに追加がなされるときには、圧縮ノードのサイズが増加する。本発明によれば、巾圧縮ノードは充填されることが許されず、そのサイズ（物理的エレメントの数即ち非ゼロポインタ）に対して上限が設定され、その後、それらはノードクラスターへと分解される。この限界は、サイズ１６のノードで１３であるのが好ましい。というのは、この限界を使用すると、付加的な効果が得られるからである。
【００１７】
図４及び５の例を参照して本発明による手順を以下に説明する。図３に基づいて巾圧縮ノードに追加がなされるときには、ノードのサイズが増加する。ある段階で、ノードは１３個のポインタを含み、これは、本発明による構造体において巾圧縮ノードに対する子ノードの最大数である（サイズ１６のノードが使用されるとき）。１４番目のポインタ（図４のＮ）がこのようなノード（図４のノードＮ４０）に追加されるときには、巾圧縮ノードは、図５に示す圧縮クオドノードのクラスターに分解され、これは、親ノードＮ５０と、４つの子ノード（Ｎ５１、・・Ｎ５４）と、孫ノードへの全部で１４個のポインタとを有する。クラスターにおけるクオドノードの各々は、サイズ１６の元のノードと同様に巾圧縮され、従って、各クオドノードは、４ビットのビットパターンを有し、各ビットは、対応エレメントがゼロポインタであるか非ゼロポインタであるかを指示する。
【００１８】
ここで、本発明によるトリー構造体は、巾圧縮ノードしかもたないものであるのが好ましい。他の点では、ノードは、論理的サイズ１６であるが、最大充填レートを越える各ノードは、巾圧縮されたクオドのクラスターに変換されている。  ここに開示する手順により、コピーコストの悪影響は、非常に効果的なやり方で回避することができる。これは、先ず、巾圧縮ノードの子ノードの最大数として値１３を選択することにより、形成されるべき親ノード（Ｎ５０）が常にいっぱいであることが確実なためである。それ故、上記ノードに対するポインタの数を検査する必要がなく、従って、この点について検索プロセスが迅速である。他方、構造体が経路圧縮を使用したとしても、形成されるべきクオドクラスターにおいては、クラスターの子ノードはいずれも経路圧縮されない。というのは、この場合に、各子ノードは、それ自身の子ノードを少なくとも２つ有するからである（クオドクラスターにおいて実行されるべき経路圧縮は、計算を遅らせる）。
【００１９】
上述した効果に加えて、値１３は、コピーコストと記憶スペース要求との間に良好な妥協を与える。このことは、ノードがサイズ１６であり且つ上述したように巾圧縮されるトリーツリーにおいてコピーコスト及びツリー記憶スペース要求を実験的に測定することにより研究されている。テストでは均一なキー分布が使用された。図６は、巾圧縮ノードの子ノードの最大数の関数としてコピーコスト（コピーされるべきワード数）を示している。最大コピーコストは、実線で示され、そして平均コピーコストは、破線で示されている。図から明らかなように、コピーコストは、構造体において充填されたノードが許される場合に先鋭に増加する。図７は、巾圧縮ノードの子ノードの最大数の関数としてトリーツリーのスペース占有度（メモリ要求）を対応的に示している。明らかなように、スペース占有度は、よりいっぱいのノードが許される限り減少する。又、図から明らかなように、本発明により進行すると、スペース占有度とコピーコストとの間に良好な妥協が与えられる。
【００２０】
図５に基づきクオドクラスターにおいて削除を行って孫ノードの数が１４未満になったときには、クラスターは、単一の巾圧縮ノードに再変換される。これが図８及び９に示されている。１つのポインタ、例えば、ポインタＫが図５のクラスターにおいて子ノードから削除されたときには、図８に示す種類のクラスターが得られ、ここでは、孫ノードの数が１３に減少している。その結果、クラスターを単一の巾圧縮ノードに回復するところのレベル圧縮が実行される。これは、図９に示すノードＮ９０を与える。
ノードの形式情報に加えて、各ノードは、エレメントテーブル（ポインタ）及びビットパターンを含むだけでよい。
図１０は、巾圧縮ノードの構造を示す。従って、圧縮ノードは、その最小構成において、３つの部分、即ちノードの形式を示す形式情報フィールド１１１と、ビットパターンを含むフィールド１１２と、エレメント（ポインタ）の数が上記に基づくエレメントテーブル１１３とを備えている。上述したノード形式に加えて、形式情報を使用して、ノードがリーフノードであるかどうか指示する。ビットパターン及びノード形式情報は、実際には、同じワードに受け入れることができ、従って、ビットパターンは、余計なスペースを必要としない。
【００２１】
始めに指示したように、上記の原理は、主として、バケットレスのトリー構造に関する。これは、本発明による解決策がバケットの場合と同じ効果（ツリーの下端でもコンパクトな構造である）を発揮するためであり、従って、全ツリーに同様のノードを使用するのが好ましい。リーフノードは、通常、データユニットを指すポインタ（又はデータユニット）を含む。しかしながら、バケットの使用が除外されることはない。
本発明によるメモリに、上記で簡単に述べた経路圧縮も組み込むことが効果的である。というのは、上記圧縮にも関わらず構造体に単一子ノードが発生されるからである。経路圧縮は、次々の単一子ノードを含む経路が深さ的に圧縮されることを意味する。経路圧縮は、既知のやり方で実施できるので、ここでは詳細に説明しない。経路圧縮の１つの種類が、本出願人の特許出願ＰＣＴ／ＦＩ９８／００１９１号に開示されている。
【００２２】
一次元ディレクトリ構造体は、ビットインターリーブ動作を使用することにより既知のやり方で多次元（一般的にｎ次元）とすることができる。ビットインターリーブ動作は、例えば、上記の国際出願ＰＣＴ／ＦＩ９８／００１９１号に開示されており、もし必要であれば、本発明に関連した背景技術はここから見出すことができよう。
以上の説明から明らかなように、本発明による機能的構造において、スタートポイントはレベル比較であり、これは、レベル圧縮ノードの充填レートが所定の限界に到達すると（即ち、コピーコストが法外なものになると）取り消される。他方、従来必須の構造体では、スタートポイントが考えられる最小ノードサイズであり、そしてノードサイズは、そのノードに対し子ノード間に充分な数の内部ノードがあるときに増加される（即ちレベル比較が実行される）。
【００２３】
図１１は、本発明によるメモリをブロック図レベルで示す。各次元が、専用の入力レジスタを有し、ひいては、全部でｎ個の入力レジスタがある。各次元のサーチキーは、参照文字Ｒ1、・・Ｒnで示されたこれらの入力レジスタに記憶され、各キーがそれ自身のレジスタに記憶される。これら入力レジスタは、レジスタＴＲに接続され、ここで、上記のサーチワードが、使用するビットインターリーブ方法に基づいて形成される。レジスタＴＲは、加算器Ｓを経てメモリＭＥＭのアドレス入力に接続される。メモリの出力は、次いで、アドレスレジスタＡＲに接続され、その出力は、次いで、加算器Ｓに接続される。最初に、各レジスタから選択されたビットは、共通のレジスタＴＲに正しい順序で読み込まれる。最初の内部即ちトリーノードの初期アドレスは、アドレスレジスタＡＲに最初に記憶され、そしてレジスタＴＲからオフセットアドレスとして得られたアドレスは、加算器Ｓにおいて初期アドレスに加算される。それにより得られるアドレスは、メモリＭＥＭのアドレス入力に供給され、そしてメモリのデータ出力は、次のノードの初期アドレスを与え、このアドレスは、アドレスレジスタＡＲにおいてそこに記憶された以前のアドレスの上に書き込まれる。その後、次に選択されたビットが再び入力レジスタから共通のレジスタＴＲへ正しい順序でロードされ、そしてそれにより得られるアドレス（インデックス）が、アドレスレジスタＡＲから得られた当該テーブルの初期アドレス（即ちトリーノード）に加算される。このアドレスも、メモリＭＥＭのアドレス入力に供給され、従って、メモリのデータ出力は、次のノードの初期アドレスを与える。上記手順は、所望のポイントがアクセスされて記録を行うか又は所望の記録を読み取ることができるまで繰り返される。
【００２４】
制御ロジックＣＬは、エレメントテーブルインデックスをレジスタＴＲから読み取りそしてそれに対応するビットをノードのビットパターンから読み取る。このビットが、非ゼロポインタに関与していることを指示する場合には、制御ロジックが、ビットパターンに基づいて物理的インデックスを決定し、そして論理的インデックスではなくそれをレジスタＴＲに記憶する。このような場合に、物理的インデックスは、（論理的インデックスに代わって）加算器Ｓにおいて、レジスタＡＲから得られたノードの初期アドレスと加算される。又、制御ロジックは、ノードの圧縮や、各ノードのレジスタから正しいビット数（２又は４）が抽出されることにも付随する。
アドレス計算の迅速さは、選択されたハードウェア構成の形式により影響され得る。進行は上記ビット操作によるものであるから、１つのプロセッサの使用から、並列処理が行われるマルチプロセッサ環境への移行により、アドレス計算を加速することができる。マルチプロセッサ環境への別の実施は、ＡＳＩＣ回路である。
【００２５】
本発明による構造体は、最下位レベルのノード（好ましくはリーフ）も、他のノード（内部ノード）と同様に圧縮されるように、実施されるのが好ましい。リーフにポインタが記憶される場合には、リーフの構造が内部ノードの場合と同様である。データユニットがリーフに記憶される場合には、リーフも内部ノードと同様に圧縮できるようにするために、それらが固定長さとなる。しかしながら、最下位レベルのノードは同様に巾圧縮されないことも考えられる。しかし、この場合、リーフにおいてサーチが低速になるために、本発明の効果の幾つかが失われる。
以上、添付図面の例を参照して本発明を説明したが、本発明は、これに限定されるものではなく、特許請求の範囲に記載された本発明の範囲内で種々の変更がなされ得ることが明らかである。本発明は、好ましいノードサイズを参照して説明したが、１６より大きな論理的サイズ、例えば、３２又は６４を有するノードにも同じ原理を適用することができる。この場合には、ノードから構成されるべきクラスターにおけるノードも、各々クオドノードより大きい。リーフノードは、通常、記憶されたデータユニットを指すポインタを含むが、別のディレクトリ構造体ではノードを指すポインタ又はデータユニットを含むこともできる。
【図面の簡単な説明】
【図１】  電話交換機に加入者データを維持するときの一次元的デジタルトリー構造体の使用を示す図である。
【図２】  ４つの非ゼロポインタを有するサイズ１６のノードを示す図である。
【図３】  巾圧縮された図２のノードを示す図である。
【図４】  巾圧縮ノードのサイズが、ノードに対してなされた追加のために大き過ぎるようになった状態を示す図である。
【図５】  図４のノードから分解されるクオドノードクラスターを示す図である。
【図６】  機能的トリー構造体においてノードの非ゼロポインタの上限の関数としてコピーコストが増加するところを示す図である。
【図７】  ノードの非ゼロポインタの上限の関数としてトリーツリーの記憶スペース要求を示す図である。
【図８】  クオドクラスターが論理的サイズ１６の巾圧縮ノードへ戻るように変化するところを示す図である。
【図９】    クオドクラスターが論理的サイズ１６の巾圧縮ノードへ戻るように変化するところを示す図である。
【図１０】  巾圧縮ノードの構造を示す図である。
【図１１】  本発明によるメモリ構成体のブロック図である。
【図１】
0003992495.tif 000002
【図２】
0003992495.tif 000003
【図３】
0003992495.tif 000004
【図４】
0003992495.tif 000005
【図５】
0003992495.tif 000006
【図６】
0003992495.tif 000007
【図７】
0003992495.tif 000008
【図８】
0003992495.tif 000009
【図９】
0003992495.tif 000010
【図１０】
0003992495.tif 000011
【図１１】
0003992495.tif 000012