米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> ヒューレット・パッカード・カンパニー

発明の名称 コンピュータメモリにインデックスを記憶するデータ構造
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2003−114816(P2003−114816A)
公開日 平成15年4月18日(2003.4.18)
出願番号 特願2002−162650(P2002−162650)
出願日 平成14年6月4日(2002.6.4)
代理人 【識別番号】100081721
【弁理士】
【氏名又は名称】岡田 次生 (外2名)
【テーマコード(参考)】
5B075
5B082
【Fターム(参考)】
5B075 MM70 NK43 
5B082 BA05 EA05
発明者 ダグラス・エル・バスキンズ / アラン・シルバースタイン
要約 課題
デジタルツリー及び同様の構成の性能特性を最適化すること。

解決手段
ブランチノード(103,108,109,119,120,121,123)の階層を備え、前記ブランチノードの各々は、適合オブジェクト(104,105,110,112,111,114-118、図2)のアレイを備え、前記ブランチノードの各々によりマップされる前記インデックスのサブエクスパンスに関連し、前記適合オブジェクトの各々は、前記適合オブジェクトのタイプを示すタイプフィールド(T)を含み、前記タイプは、ポインタタイプ及び前記インデックスの少なくとも1つが前記適合オブジェクトに記憶された即時タイプ(図2−6)を含み、前記ポインタタイプには、他ノードへのポインタ(116B)及び前記他のノードについての情報を記憶する情報データフィールド(116A)を含むデータ構造。
特許請求の範囲
【請求項1】コンピュータメモリにインデックスを記憶するデータ構造であって、トップレベルブランチ103から開始して複数レベルへと順序づけられたブランチノード(103,108,109,119,120,121,123)の階層を備え、前記ブランチノードの各々は、適合オブジェクト(104,105,110,112,111,114-118、図2)のアレイを備え、前記ブランチノードの各々によりマップされる前記インデックスのサブエクスパンスに関連し、前記適合オブジェクトの各々は、前記適合オブジェクトのタイプを示すタイプフィールド(T)を含み、前記タイプは、ポインタタイプ及び前記インデックスの少なくとも1つが前記適合オブジェクトに記憶された即時タイプ(図2−6)を含み、前記ポインタタイプには、他ノードへのポインタ(116B)及び前記他のノードについての情報を記憶する情報データフィールド(116A)を含むデータ構造。
発明の詳細な説明
【0001】
【発明の属する技術分野】本発明は、一般的にデータ構造の分野に関し、特にデータ組織の構造が記憶されたデータに依存し、情報がポインタに関連する階層的データ組織に関する。
【0002】
【従来の技術】コンピュータのプロセッサ及び関連するメモリは、速度が増加し続けている。ハードウェアが物理的な速度の限界に近づくにつれ、しかしながら、データのアクセス時間をはっきりと減少させることが要求される。かかる限界が主たる要因でなくとも、ソフトウェアの効率を最大化させることで、ハードウェアプラットフォームの効率を最大化させ、ハードウェア/ソフトウェアシステム全体としての能力を拡大する。
【0003】システムの効率を上げる1つの方法は、効率的なデータ管理によるものであるが、データ構造の適切な選択、関連しての格納、検索アルゴリズムにより達成される。例えば先行技術の、様々なデータ構造、関連しての格納、及び検索アルゴリズムは、アレイ、ハッシング、2分木(バイナリーツリー)、AVLツリー(高さのバランスをとった2分木)、b-ツリー、及びスキップリストを含むデータ管理のため開発されてきている。
【0004】これらの先行技術である、データ構造、関連しての格納、及び検索アルゴリズムのそれぞれでは、アクセス時間の高速化とメモリのオーバヘッドの最小化の間に固有のトレードオフが存在している。例えば、アレイは、単一アレイ要素のアドレス計算を通して高速インデックス化に備えているが、単一の値が格納される前にメモリ内でアレイ全体を予め配置することを要求し、そしてアレイの未使用インターバルがメモリ資源を浪費する。代わりに、二分木、AVLツリー、bツリー、及びスキップリストは、データ構造のためにメモリを予め配置しておくことを要求し、未使用メモリの配置を最小限にするよう試みるが、ポピュレーションが増加するに伴い、アクセス時間が増加することが明らかになる。
【0005】アレイは、簡略化された構造を有し、格納されたデータの高速アクセスに備えた従来技術のデータ構造である。メモリはアレイ全体に配置されなければならないが、その構造は柔軟ではない。アレイの値は、アレイの各要素に配置されたインデックスをサイズ毎に増やし、アレイの基礎アドレスのオフセットを加えることで、各位置毎に数値単位で調べられる。
【0006】典型的には、単一の中央演算処理装置のキャッシュラインフィル(cache linefill)が、アレイ要素及びここに格納された値にアクセスするにあたり必要とされている。説明され、典型的に具現化されているように、アレイは非効率であり、比較的柔軟でないメモリである。しかしながら、アクセスはO(1)として与えられる。すなわち、アレイサイズから独立して(ディスクスワップを無視して)いる。
【0007】代わりに、前に説明したデータ構造は、二分木、b-ツリー、スキップリスト及びハッシュテーブルを含んでおり、メモリは効率的であるが望ましくない特徴を含んだ形で利用可能となる。例えば、ハッシングは、散在した、多分に多重ワードとなるインデックス(例えばストリング等)を、アレイインデックスに変換するのに用いられる。典型的なハッシュテーブルは、サイズ固定のアレイであり、そこへの各インデックスは、オリジナルインデックスで実行されたハッシングアルゴリズムの結果である。
【0008】しかしながら、ハッシングを効率的にするために、ハッシュアルゴリズムは格納されるべきインデックスにマッチさせなければならない。ハッシュテーブルはまた、全てのデータノードがオリジナルインデックスのコピー(又はこれのポインタ)を含むことを求めているので、各シノニムのチェーンにおけるノードを識別することができる。アレイのように、ハッシングを用いるためにはメモリを予め配置しておくことを必要とするが、もし適切に設計されている場合、すなわち格納されるべきデータの特徴が、はっきり分かるものであり、動作し、具現化されるハッシングアルゴリズム、衝突解消技術、及び格納構造にマッチする場合、フラットなアレイに対して配置されなければならないのはメモリの一部分である。
【0009】特に、デジタルツリー、又はトライ(trie)は、データへの高速アクセスを提供するが、一般的にメモリは非効率である。ツリーブランチを狭く維持することで、散在したインデックスのセットを処理すべく、メモリ効率を高めてもよいが、その結果ツリーが深くなり、メモリの参照、迂回、及びキャッシュラインフィルの平均数が増加し、その結果データへのアクセスが遅くなる。この後者の要素、すなわち、キャッシュ効率を最大化することは、かかる構造がまだ議論されているときにしばしば無視されるが、システム性能に影響を与える支配的な要素となる場合がある。
【0010】トライは小さなアレイ又はブランチのツリーであるが、ここで各ブランチはインデックスの1つ又はそれ以上のビットを復号する。先行技術のデジタルツリーは、単純なポインタ又はアドレスのアレイであるブランチノードを有する。典型的には、ポインタ又はアドレスのサイズは、デジタルツリーのメモリ効率を改善すべく最小化される。
【0011】デジタルツリーの「後尾」で、最終ブランチは最終ビットのインデックス、及びインデックスに特定のストレージへの要素点を復号する。ツリー(木)の「リーフ(葉っぱ)」は、特定インデックス用のこれらメモリチャンクであり、特定用途向けの構造を有している。
【0012】デジタルツリーは、インデックスがなかったり、ポピュレーションゼロ(又は空となるサブエクスパンスと呼ばれる)となるブランチに、メモリを割り当てる必要がないという利点を有している。この場合において、空のサブエクスパンス(subexpanse)を指すポインタは、固有値が与えられ、有効なアドレス値を表してはいないことを示すヌルポインタと呼ばれる。
【0013】さらに、デジタルツリーに格納されたインデックスは、近隣の識別を許容し、ソートされた順序でアクセスすることができる。ここで用いられるデジタルツリーの「エクスパンス(expanse)」は、デジタルツリー内に格納可能な値のレンジであるが、ここでデジタルツリーのポピュレーション(population)は、ツリー内に実際に格納される値の集合である。
【0014】同様に、デジタルツリーのブランチのエクスパンスは、ブランチ内で格納できるインデックスのレンジであり、そしてブランチのポピュレーションはブランチ内に実際に格納される値(例えばカウント)の数である。(ここで用いられるように、「ポピュレーション」という語は、インデックスの集合又はそれらのインデックスのカウントのいずれかについていうものであるが、この語の意味は、この用語の用いられる文脈において当業者に明らかなものである。)Acharya、Zhu及びShenによる、「Adaptive Algorithms for Cache-efficientTrie Search」では、トライ検索のためのキャッシュ効率アルゴリズムを説明している。各アルゴリズムは、異なるデータ構造を用いているが、この構造は、トライにおいて異なるノードを表すための、仕切られたアレイ、B-ツリー、ハッシュテーブル、及びベクトルを含んだものである。選択されたデータ構造は、ノードのファンアウトと同様に、キャッシュ特性に依存している。
【0015】アルゴリズムはさらに、ノードを表すのに用いられるデータ構造を動的に切り替えることで、ノードのファンアウトの変化に適合している。最後に、各データ構造のサイズ及びレイアウトは、キャッシュ特性と同様にアルファベット記号のサイズに基づいて決定される。この刊行物ではさらに、現実の及びシミュレートされたメモリ階層の性能評価を含んでいる。
【0016】他の刊行物で当業者に知られ、用いられ、データ構造について説明しているものとしては、次のものがある。Fundamentals of Data Structures in Pascal、第4版、HorowitzとSahni;pp582-594;The Art of Computer Programming、第3巻;Knuth;pp490-492;Algorithm in C、Sedgewick、pp245-256、265-271;「Fast Algorithm for Sorting and Searching String」;Bentley、Sedgewick;「Ternary Search Trees」;5871926、INSPEC概要番号:C9805-6120-003;Dr.Dobb's Journal;「Algorithm for Trie Compaction」、ACM Transanctions onDatabase Systems、9(2):243-63、1984;「Routing on longest-matching prefixes」;5217324、INSPEC概要番号:B9605-6150M-005、C9605-5640-006;「Someresults on tries with adaptive branching」;6845525、INSPEC概略番号:C2001-03-6120-024;「Fixed-bucket binary storage trees」;01998027、INSPEC概要番号:C83009879;「DISCS and other related data structures」;03730613、INSPEC概要番号:C90064501;そして、「Dynamic sources in informationtheory:a general analysis of trie structure」;6841374、INSPEC概要番号、B2001-03-6110-014、C2001-03-6120-023。
【0017】拡張ストレージ構造は、米国特許出願番号09/457164、1999年12月8日出願、タイトル「A Fast Efficient Adaptive, Hybrid Tree」(以下、164特許出願とする)で、直前の出願と同様に出願されている。ここで説明されているデータ構造及びストレージ方法は、自己同調を行い、「エクスパンス」ベースのストレージノードを配置して格納要件の最小化を行う、自己適合構造を備えており、効率的でスケーラブルなデータ格納、調査及び検索能力を提供する。ここで説明される構造は、しかしながら所定データ分布状況を充分に利用するものではない。
【0018】前記特許出願で説明されている格納構造の拡張は、次の出願において詳述されている。それは、米国特許出願番号09/725373、出願日2000年11月29日、タイトル「A Data Structure And Storage And Retrieval Method Supporting Ordinality Based Searching and Data Retrieval」で、直前の出願と同様に出願されている。この後者の特許出願では、データ構造、関連するデータの格納、及び検索方法を記述しているが、この検索方法は、格納された又は順序化された要素の階層構造により参照された要素のカウント、その構造における序数値に基づいた要素へのアクセス、及び要素の順序性の識別を迅速に提供するものである。
【0019】順序化したツリーで具現化した構造において、各サブツリーに存在するインデックスのカウントが格納される。すなわち、各サブツリーの根本(cardinality)が、高レベルノードで、又はこれに関連して格納される。この高レベルノードは、そのサブツリーを指すか、又はサブツリーの頭のノードにおいて又はこれに関連している。データ構造の特定要件(例えば、新ノードの作成、ポインタの再割当て、バランス化等)に加え、データの挿入及び削除は、カウントに影響を与える更新ステップを含んでいる。
【0020】
【発明が解決しようとする課題】しかしながら、本構造は、所定のまばらなデータ状況を充分に利用できない。従って、デジタルツリー及び同様の構成の性能特性を最適化する技術及びツールに対する必要が存在する。
【0021】
【課題を解決するための手段】本システムは、メモリに記憶され、ダイナミックアレイとして扱われ、そしてルートポインタを通してアクセスされるデータ構造を含む。空のツリーについては、このルートポインタはヌルであるが、そうでなければそれはブランチノードの第1階層を指す。各ブランチノードは、情報を有するすなわちリッチな複数のポインタにより構成されるが、このポインタは、データ構造をアクセスするのに用いられたインデックス(キー)のエクスパンスを細分する。各リッチポインタは、従(子)ブランチノード又はリーフノード(又はこれを指すポインタ)のアドレスに加えまたは場合によってはこの代わりに補助情報を含んでいる。この補助情報は様々な最適化をできるようにしている。この最適化の結果、この情報を記憶するのに空間が必要にもかかわらず、ポジティブな「投資に対する回収」につながる。
【0022】情報を有するポインタは、アドレス(子ブランチ又は子リーフノードを実際に指すポインタ)、ツリー中のレベルをスキップする又は現在レベルへのリーフ情報をもたらすようにするインデックスのディジット(キーのパーツ)、ツリー中又は全てのサブエクスパンス(インデックスのレンジ)の有効な(記憶された)インデックスの数を素早くカウントするのを助けるポピュレーションのカウント、ポインタが指すツリー中の次レベルがあるときは、そのレベルについてのタイプ情報、を含むことができる。
【0023】ポインタはまた、動作、データの統合、及びエラーの修正を認証する情報を提供してもよい。状態情報は、その結果のリッチポインタが状態情報を提供するよう、ポインタにバンドル(bundle)してもよい。この場合、データ構造は、データを記憶し処理する手段を提供するだけでなく、本構造を用いた処理をサポートする設備を含めることができる。この情報を含めることで、デジタルツリーが様々な方法で圧縮されるようになる。その方法は、それを小型化し、よりキャッシュ効率をよくし、そしてアクセス及び修正速度を上げる。ブランチノードが、もしかすると従属ノードへのポインタの単純アレイではもはやないとしてもである。この情報はまた、データ破損に加えて、ツリーへの高速アクセス及び修正をできるようにする構造及び冗長性を提供する。
【0024】
【発明の実施の形態】上述のように、典型的なデジタルツリーはいくつかの不都合な点がある。この不都合な点は、ブランチのサイズ(すなわち「ファンアウト」)が小さくなってこれらのヌルポインタの数が減るのに対し、メモリ参照又は間接参照、及び場合によってはキャッシュラインフィルの数が増える一方、メモリが空ブランチに関連したヌルポインタに割り当てられていることである。デジタルツリーに関連するこうした不都合点は、従来のコンピュータアプリケーションの利用を制限してきた。
【0025】本発明は、デジタルツリーの利点を、ツリー中の非ターミナルノード(ブランチ)とターミナルノード(リーフ)の両方を処理する賢明なアプローチと組み合わせる。こうした賢明なアプローチは、データ構造に記憶されたデータのルックアップ、挿入、及び修正の全てに対して、メモリ空間及び処理時間を最小化する。さらに本発明は、インデックスがデータ構造に追加され又は削除されるので、データ構造が効率的であることを確保している。本発明により用いられるアプローチは、データの圧縮及び短縮の形式を含み、データ構造に必要なメモリを減らすようにし、必要とされるキャッシュラインフィルの数を最小化し、アクセス及び検索回数を減らす。
【0026】本発明は、ここで「情報を有するポインタ」と呼ばれそしてそれをもって交換可能である、「リッチな」ポインタを含むデジタルツリーで典型的に具現化され、追加情報をポインタの書き直し又はアドレス情報に関連付ける単一ポインタの置き換えを行う。この追加情報は、データ構造やその構造にアクセスするプロセスによって使用してもよい。デジタルツリー内でのリッチポインタの使用は、データ構造内で様々な最適化をできるようにしている。本発明の好ましい実施形態において、デジタルツリーブランチの各リッチポインタは、典型的に2ワードを占める複数のセグメント又は部分を含む。リッチポインタは、アドレス(実のポインタ)、インデックスのディジット(キーのパーツ)、ポピュレーションのカウント、ツリー内でポインタが「指す」又は指示される次のレベルに関連するタイプ情報、エラー検出をサポートする冗長データ、状態情報等を含んでもよい。
【0027】リッチポインタの1つのタイプとして、狭エクスパンスポインタがある。特に、データ圧縮の一形式は、全てが先導ビットを共通に持ったインデックスによる「密集したクラスタ」で、エクスパンスが中身を持つようになるときに用いられる場合があり、本発明に係る狭エクスパンスポインタによりサポートされている。
【0028】複数のデジタルツリーブランチを経由した共通ビット(又はリーフの冗長ビット)の典型的表現は、共通ビットをブランチ又はリーフへのポインタの一部又はこれに関連したものとして表現する(例えば符号化する)ことにより置き換えることができる。
【0029】本発明の好ましい実施形態においては、このタイプのデータ圧縮は、共通の先導全体バイトに限定されている。共通ビットはリッチポインタに記憶され、ポインタタイプは、次のオブジェクトにおける残った未復号のディジットの数のレベルを示す。残った未復号のディジットは、狭ポインタによりスキップされたレベルの数を意味している。リッチポインタは次のレベルを指すポインタと共に記憶され(すなわち関連する)、そうでない場合よりも小さいエクスパンスを有している。好ましくは、各サブエクスパンスポインタは、最初のバイト以外について復号された全てのインデックスを保持した「復号」フィールドを含んでいる。狭ポインタは、デジタルツリー内でレベルをスキップし、インデックスを記憶するのに用いられるメモリを節約し、そして必要とされるメモリ参照及びキャッシュラインフィルの数を減少する方法を提供する。
【0030】図1A〜1Eは、デジタルツリーにおける狭エクスパンスポインタの使用について説明している。(本説明の目的のため、発明となるデータ構造が、32ビットワードサイズプラットフォームを参照して与えられる。ここでインデックスは単一ワードである(例えば恣意的な長さの文字ストリングとは逆である)が、一方本発明はこれに限定されるものでなく、逆に、他のワードサイズ及び配置を実現する。このワードサイズ及び配置は、16、32、64、及び128ビットのワードサイズを含むものであるがこれに限定されるわけではないことを理解されたい。)
ここで用いられるように、「スロット」という用語は、アレイのセルの記録又はグループのことを呼ぶ。アレイのセルの記録又はグループは、子ノードへのポインタ、又はより一般的にはインデックスのサブエクスパンスに関連しこれを含み、ポインタに関連する全てのデータと一緒となるものである。一般的にアレイは「インデックス化」し、その結果各セル又は「スロット」は、アレイ内のスロットの序数値に対応したオフセット値に結びつく。従ってより詳細には、ルートポインタノード101は、デジタルツリーの基礎データ構造にアクセスするのに用いられている。
【0031】ルートポインタノード101はアドレス情報102を含むが、これは、第1又は「トップ」レベルノード103、この説明においてはブランチノードを指す矢印として図で示されている。(補足すると、ここで用いられている専門用語は「レベル1」としてルートにより示されているツリーのトップノードをラベル化する。ここで、レベル1ノードの子は、「レベル2」ノードとされる。)この取り決めによると、全てのブランチノード又はリーフノードは、そのノードの上で記憶されたインデックスにおいて復号された1つ以上の数のディジット(バイト)に等しい。さらに補足すると、この取り決めは、代表的ではあるが、本説明の目的のためであり、例えばリーフノードをツリーの第1レベルを構成するものとすることを含め、他の取り決めを採用してもよい。
【0032】この後者の場合、本発明の好ましい実施形態では、全てのブランチノード又はリーフノードは、記憶されたインデックス中又はそのノード以下で復号されるべく残っているディジットに等しい。第1ノード103は、256までの低レベルノードについてのスロット又は拡張ポインタアレイを含み、256に分かれたブランチを具現化することによるデータ構造のエクスパンス全体、すなわち16進数で00000000からFFFFFFFFのインデックスを表す。(補足すると、本発明の好ましい実施形態では各ブランチにおいて1バイトのインデックスを復号するが、他の部分のインデックスを、例えば4ビットを復号して各レベルのツリーで16に分かれたブランチを具現化すること等を含め使用してもよい。)
第1レベルノード103は、エクスパンス00000000から00FFFFFFに対応する(適合オブジェクトを含む)第1スロット104、及びインデックスFF000000からFFFFFFFFを含む最終エクスパンス部分に対応する最終スロット105を含む。スロット104のポインタフィールドに含まれるポインタは、次レベルのサブエクスパンス(デジタルツリーのレベル2)の256のうち最初の1つを指す一方、スロット105のポインタは、レベル2の最も上位の上方1/256番目を指す。
【0033】レベル2の第1エクスパンスは従属ノード108を含み、一方従属ノード108は、低レベルノード119、120を指す256のポインタのアレイを含む。示したように、ノード108(すなわち16進数で000000000-00FFFFFFのレンジのインデックス)によりカバーされたエクスパンスは、第3レベルノード119及び120(すなわち16進数でそれぞれ00000000-0000FFFF及び00100000-0010FFFF)によりカバーされるサブエクスパンスレンジ内に下りるインデックスにより、まばらに中身を持つだけである。
【0034】従って、スロット110及びスロット112のポインタは、ノード119及び120(すなわちこれのアドレス)への有効な向け直し情報を含む一方、ノード108の残った254のポインタは、16進数で00FF0000-00FFFFFFの最上位のエクスパンスレンジをカバーするスロット111のポインタを含め、ヌルポインタである。すなわち、どのターゲット位置又は空ノードも指していないポインタについて予約された特定値を有する。
【0035】補足すると、ノード120は、16進数で00100200-001002FFのレンジに対応し、ノード120の唯一のアクティブポインタ、すなわちポインタ122により指された単一サブエクスパンスノード121内に下りる全てのインデックスにより、同じようにまばらに中身を持つ。従って、ノード120が256のポインタについて追加格納空間の配置を要求するだけでなく、それによってリーフノードに参照されたインデックスへのアクセスは、2つの間接参照及びそれゆえ2つのキャッシュフィルを必要とする。
【0036】従って、図に示したように、スロット110は、00000000-0000FFFFに対応するレベル3スロットへのポインタを含む。さらに、スロット112は、00100000-0010FFFFと相関するレベル3の分かれたサブエクスパンス120を指すポインタを含む。同様に、レベル3内のスロットは、さらにレベル4のサブエクスパンスを指してもよい。操作上、図1A-1Eにおけるレベル4には、インデックスの1バイト部分を連続して復号すること、復号値に対応したツリーを巡回する(traverse)ことにより達する。
【0037】第1バイト(00)は、スロット104を識別するのに用いられ、レベル1から対応するレベル2の部分、すなわちスロット104のポインタによりアドレスされたノードでツリーを巡回するための対応するポインタを含む。次のバイト(10)は、スロット112を識別するのに用いられ、ノード108からレベル3の従属ノード120へのツリーを巡回する対応ポインタを含んでいる。次のバイト(02)は、スロット122を識別するのに用いられ、レベル3のノード120から、レベル4のノード121のツリーを巡回する対応ポインタを含んでいる。
【0038】レベル4では一旦、インデックス値に対応するデータを検索すべく、残ったバイトが、ノード121の適当なスロットにアクセスするのに使用される。説明したように、この処理は4つの分割メモリ参照、及び潜在的に、インデックスに対応する正しいメモリアドレスを識別するための4つの異なるキャッシュラインフィルを必要とする。
【0039】エクスパンス又はサブエクスパンスが、少ない数の密集した従属インデックスのクラスタによりまばらに中身を持つ場合、リッチポインタは、中身のあるサブエクスパンス又はインデックスの共通ビットを符号化するのに用いてもよい。図1A〜1Eを参照すると、レベル2従属ノードの上方1/256サブエクスパンスが、それぞれFF100200-FF1002FFのレンジ内にわたる、インデックスによる密集したクラスタを含む。上方1/256サブエクスパンスの他の部分、FF100000-FF1001FF及びFF100300-FF10FFFFは、インデックスを含まない。この場合、リッチポインタは、サブエクスパンスのレベル4部分を直接指すのに用いることができ、レベル3をスキップし、レベル3へのメモリ参照や間接参照の必要をなくす。
【0040】特に、対応するスロット116は、次のサブエクスパンス又は従属インデックスにアクセスするための他の構造を指す、情報データフィールド116A及びポインタノード116Bを含んだリッチポインタノードを含む。情報データフィールド116Aは、残ったインデックス02の共通バイト(すなわちインデックス部分)を含む。それは、残ったインデックス全てがFF100200-FF1002FFのレンジ内に下りるからである。
【0041】この場合、リッチポインタはメモリ参照の1つそしておそらくは1つのキャッシュフィルを除去する。インデックスの最初の2バイト(FF)は、ツリーのレベル1からレベル2の適当な部分まで巡回するのに用いられる。レベル2ノードにおいて一度、リッチポインタは、レベル2ノードから直接レベル4ノードまで巡回するのに用いられる。
【0042】かかるリッチポインタ構造は、少なくとも2つのタイプのリッチポインタ又は適合可能なオブジェクトを網羅するが、これは上述のポインタタイプ、及び即時タイプを含む。即時タイプは、即時リーフ又は即時インデックスをサポートする。すなわち、エクスパンスのポピュレーションが比較的まばらであるとき、リッチポインタは、デジタルツリーブランチ内で、「即時」にインデックスを記憶するために用いられ、インデックスにアクセスするためのデジタルツリーの最低レベルへの通過を必要としない。このフォーマットは、即時機械語命令と同種のものであり、ここで命令は、全ての変位バイトにすぐ続く即時オペランドを特定する。
【0043】従って、即時インデックスすなわち数が少ないインデックスは、ノード中に記憶され、1つ又はそれ以上の向け直しを回避し、さもなければツリーの通過にあたり必要とされ、そして離れたリーフノードに到達する。それにより即時インデックスは、より多くのメモリを配置して多重なメモリの参照及びデータアクセスのための可能なキャッシュフィルを要求する代わりに、小さいポピュレーション(又は少ない数のインデックス)をパックする方法を、リッチポインタ構造に直接与える。
【0044】好ましい実施形態による2ワードフォーマットは、即時インデックスを含めることを直ちにサポートする。このことは、リッチポインタ内で、情報データフィールドのインデックスディジットを記憶することにより達成される。32ビットシステムで具現化されたリッチポインタは、3バイトの単一即時インデックスから7つの1バイトインデックスまでの、どこで記憶してもよい。一方、64ビットシステムのリッチポインタは、1バイト即時インデックスを15まで記憶してもよい。
【0045】即時インデックスをサポートするリッチポインタの一般化された構造は(適合オブジェクトとも呼ばれる)、図2で示される。リッチポインタは、プラットフォームのワードサイズ及びインデックスのサイズに依存した、1つ又は複数のインデックス“I”と、インデックスのサイズ及び即時インデックスの数の符号化を行う8ビットタイプフィールドを含む。
【0046】上述のように、記憶された即時インデックスの数が依存するのは、インデックスのワードサイズ、より大きいインデックスを必要とするルートに最も近いツリー内の上方レベル、ツリーがリーフへと巡回されるときに見つけられるより小さいインデックスである。
【0047】例としてあげる様々なサイズの即時インデックス値の数は、好ましい実施形態にかかる32ビット及び64ビットマシンに収容され、図3に示す。ここで、インデックスは有効/無効指示器へとマップされ、関連値を持たない。図4A-図4Dは、3、2、1バイトインデックスを示しているが、即時リッチポインタ構造に記憶され、32ビットプラットフォーム上で具現化されたものである。一方図5A-Hは、64ビットマシン上で具現化された7から1バイトのインデックスサイズを示している。図4A-D及び図5A-Hの構造はまた、本発明の実施形態を指しているが、ここでは、インデックスが存在するか存在しないかのみが、インデックスに関連する他の値を伴わずに示される。
【0048】図6A-Dは、64ビットマシンにおける他の実施形態を示しているが、ここで値は各インデックスIに対応している。この実施形態によれば、7バイトまでの単一即時インデックスIがリッチポインタ構造に記憶されるとき、インデックスに関連する64ビット値はまた、図6Aに示すように記憶される。しかしながら、インデックスが3バイト、2バイト、又は1バイトインデックス(それぞれ図6B-6C)として表されるときなど、1つ以上の即時インデックスが記憶される場合、リッチポインタの最初の8バイトワードは、各複数のインデックスに対応する値を指すポインタとして代わりに用いられる。本発明が32ビットマシンで具現化される場合、インデックスに関連する値を記憶すべく、同様の構成が用いられる。
【0049】即時インデックスは、リッチポインタにパックされるが、リッチポインタは、「第1バイト」(タイプフィールドからは最も遠い)のところではじまり、ストレージを未使用のままにする。好ましい実施形態の例外では、単一即時インデックスが記憶される場合、インデックスが第2ワードの第1バイトにおいて始まり、第1ワードを、インデックスをある値にマップするこれらのアレイ(図4A、図5A、及び図6A参照)について、インデックスに対応する値領域になるようにしている。一度開始アドレス、インデックスサイズ、ポピュレーションが分かると、即時インデックスを含むリッチポインタの通常リーフ及びインデックス部分は、同一になる。
【0050】従って上述のように、即時インデックスリッチポインタ構造は、小さなリーフを含むものと考えてもよい。かかる構造は、インデックスがリッチポインタ自身の中にあるまばらに中身を持っているエクスパンスを表すにあたり、特に助けとなる。
【0051】図7A-Eは、典型的なポインタと即時インデックスを記憶するのに用いることができるリッチポインタの間の比較を示している。インデックスは典型的には、対応するアレイセル又は「スロット」のレベル4ノード121の一部に記憶される。リッチポインタを即時インデックスとして用いることにより、リーフノード701等のリーフノード内に別にあるインデックスが、例えばレベル2ノード109などより高いレベルのノードの対応する部分に、代わりに記憶される。64ビットシステムにおいては、1つ又はそれ以上のインデックスを、即時インデックスデータフィールド702におけるレベル2ノード109のスロット116に、記憶することができる。図示するように、スロット116は、論理上複数のサブスロットに分割され、それぞれ即時インデックスを記憶する。リッチポインタを即時インデックスとして使用することで、少なくとも1のメモリ参照と1又は複数のキャッシュラインフィルを回避する。
【0052】リッチポインタと共に利用可能な情報を有するフィールドをもう一度利用することで、オブジェクトに関連する状態情報を記憶する。オブジェクトは、ポインタにより参照されるか、若しくは構造にアクセスする手順の状態等、状態情報を記述したり記憶したりする。
【0053】従って、ツリー自身はステートマシン(状態機械、state machine)ではないが、挿入、削除、検索のための特定インデックスと組み合わせ、コードをステートマシンと同じように処理できるようにするアクセス処理への入力として用いてもよい。ツリーサブエクスパンスポインタはそれぞれ、順に挙げられたオブジェクトタイプの大きい数(例えば256)の1つを符号化する「タイプ」フィールド(例えば8ビット)を含む。ツリー中のレベルは直接目録において符号化される。
【0054】リッチポインタは、多くの数の、かなり特定された次レベルオブジェクトタイプであるリッチポインタタイプを許容する。ツリー巡回コードを、その入力が復号すべきインデックス/キー及びツリーのノードとなるステートマシンとして考えることもできる。好ましい実施形態においては、ステートマシンアルゴリズムは、単一大スイッチのようになるソフトウェアを備え、ソフトウェアが小さく高速なチャンクコードの収集として動作できるようにしており、それぞれ、最小のランタイム計算でうまく1つのタスクを実行すべく予め最適化されている。ツリーレベルは各ポインタタイプにおいて符号化されているので、巡回コードは、カレントツリーレベルをトラックする必要がない。代わりに、この状態情報はツリー自身のノード内に記憶されている。
【0055】リッチポインタはまた、情報を冗長にすることで、データ、解釈、及びデータ処理などにおけるエラーを検出するのに用いてもよい。すなわち、リッチポインタの一部として記憶される情報を特徴付けるデータは、エラー検出コードが用いられるときに、参照される多くのデータ中のエラーを検出するにあたり用いてもよい。この情報はまた、例えば、レベルを符号化することによるツリー中の位置、又はリッチポインタを形成するための各ポインタに関連した同様の情報、を適合するのに用いてもよい。
【0056】特に、実際リッチポインタからの全ての未使用ビットを全て符号化することは、可能でもなく望ましくもない。機械語命令の効率は、部分的にワード及びバイト境界に依存している。CPU命令時間に対するキャッシュフィルタイムの率は、キャッシュ効率が重要となる程度に十分高い一方、例えばディスク読みだしの最小化を目的とした、他のデータ圧縮方法に比較して一般的に依然として低い。(キャッシュ効率プログラムは、「完全な」データ圧縮に対してCPU時間をバランスさせなければならない。)
「不完全」圧縮の結果、リッチポインタ中の冗長データを提供し用いるようになる。冗長データは、ツリー巡回コードが、臨機応変だがとても「安く」、ツリー自身における多くのタイプのデータ破損を検出し報告できるようにするものであり、ツリー管理コードの欠陥又は外部事故のいずれかにより発生する。好ましい実施形態において、破損が安く検出される結果、空ポインタとして戻る場合がある一方、「高価に」検出する結果、デバッグコードにおいてのみアサーションエラー(assertion failure)となり、生成コードにおいては無視される。
【0057】例えば、エラー状況は、ポインタタイプがツリーレベルにマッチすることを知るべくチェックすることにより、識別してもよい。例えば、「リーフ1」オブジェクト等の所定オブジェクトが、ルートから最も遠い最小レベルのツリー以外で現れることは適切ではない。図7A-7Eを参照すると、タイプフィールド703が255等の無効値を含む場合、無効リッチポインタタイプが示され、実行されるエラー処理を適正化する。
【0058】別のチェックは、狭ポインタの一部として必要とされないすでに復号されたインデックスバイトを含め、サブエクスパンスポインタ中の復号バイトについてなされる。にも関わらず、ツリー中のこの点に導くパス(path)にマッチしなければならない。この方法で既に復号されたインデックスバイトを記憶すること、そしてなんとかして必要とされた狭ポインタバイトのみの記憶に対して最適化することは、より効率的であり、簡単である。
【0059】リッチポインタはまた、計算を効率化できるようにする。特に、単一即時インデックスがリッチポインタに記憶されるとき、ただ残留未符号バイトだけでなく、インデックスの第1バイト以外の全てを記憶する余地がある。このことで高速巡回及び修正が可能となる。復号バイトと同様、これらの冗長バイトは即時インデックスへと巡回されたパス(path)と一致しなければならない。
【0060】リッチポインタはまた、ポインタの可搬性(portability)をサポートしている。すなわち、狭エクスパンスポインタが、スキップされるレベルの数ではなく従属ノードのレベルのみを示すとき、それは「可搬性」のままとなる。それが参照するオブジェクトについて「知って」いるが、それがあるオブジェクトについて「知って」いるわけではない全てのリッチポインタと同様、可搬狭エクスパンスポインタは、「外れ値(outlier)」インデックスが挿入又は削除されたとき、より容易なブランチ挿入及び削除をできるようにする。外れ値はインデックスであるが、狭エクスパンスポインタにより占有され、スロットの中身のあるサブエクスパンスの下に属し、そのポインタの存在している狭エクスパンスの下に属するわけではない。
【0061】図8は、本発明に係るデータ構造を具現化し、維持するメモリ格納プログラムをサポートし、走らせることのできる、コンピュータシステムの概略図である。従って本発明は、幅広いデータ構造、プログラム言語、オペレーティングシステム、ハードウェアプラットフォーム及びシステムに適用可能であり、図8は、本発明をサポートするのに適したプラットフォームを含んだ、かかるコンピュータシステム800を示している。
【0062】コンピュータシステム800は、システムバス802に結合した中央演算処理装置801を含む。CPU801は、HP PA-8500又はインテルペンティアムプロセッサのような、一般的な用途のCPUとしてもよい。しかしながら、CPU801が、例えばポインタの使用など、ここで説明された工夫された動作をサポートする限り、本発明はCPU801のアーキテクチャに拘束されるわけではない。システムバス802は、ランダムアクセスメモリ(RAM)803に結合されるが、これはSRAM、DRAM、又はSDRAMとしてもよい。
【0063】ROM804はまた、システムバス802に結合されるが、PROM、EPROM、又はEEPROMとしてもよい。RAM803及びROM804は、ユーザ、システムデータ、及びプログラムを業界において知られたものにする。
【0064】システム802はまた、入出力(I/O)制御カード805、通信アダプタカード811、ユーザインターフェースカード808、及びディスプレイカード809に結合される。I/Oカード805は、ハードディスクドライブ、CDドライブ、フロッピー(登録商標)ディスクドライブ、テープドライブ、といったストレージデバイス806をコンピュータシステムに接続する。通信カード811は、コンピュータシステム800をネットワーク812に結合するよう適合されるが、ネットワーク812は、電話ネットワーク、ローカル/ワイドエリアネットワーク(LAN/WAN)、イーサネット(登録商標)ネットワーク、インターネットネットワークとしてもよく、有線又は無線とすることができる。ユーザインターフェースカード808は、キーボード813、ポインティングデバイス807、等のユーザ入力デバイスをコンピュータシステム800に結合する。ディスプレイカード809は、CPU801により駆動し、ディスプレイ装置810を制御する。
【0065】本発明は、現在好ましい実施形態と考えられるものとの関係で説明してきたが、本発明は開示された範囲に限定されるものではなく、逆に付された特許請求の範囲の趣旨及び範囲内に含まれる様々な修正や同等の配置をカバーすることを意図してることを理解すべきである。この発明は例として、次の実施形態を含む。
【0066】(1)コンピュータメモリにインデックスを記憶するデータ構造であって、トップレベルブランチ(103)から開始して複数レベルへと順序づけられたブランチノード(103,108,109,119,120,121,123)の階層を備え、前記ブランチノードの各々は、適合オブジェクト(104,105,110,112,111,114-118、図2)のアレイを備え、前記ブランチノードの各々によりマップされる前記インデックスのサブエクスパンスに関連し、前記適合オブジェクトの各々は、前記適合オブジェクトのタイプを示すタイプフィールド(T)を含み、前記タイプは、ポインタタイプ及び前記インデックスの少なくとも1つが前記適合オブジェクトに記憶された即時タイプ(図2−6)を含み、前記ポインタタイプには、他ノードへのポインタ116B及び前記他のノードについての情報を記憶する情報データフィールド116Aを含むデータ構造。
【0067】(2)従属ノード(123)が、データ構造においてその親(109)より1以上のレベル分下となり、かつ前記従属インデックスの共通部分を符号化しないよう、前記情報データフィールド(116A)が、前記インデックスのうち従属部と共通であるインデックス部分を示す請求項1に記載のデータ構造。
【0068】(3)ポインタフィールド(116B)は、前記データ構造の1レベルの前記ポインタタイプの前記適合オブジェクト(116)のうち1つに関連し、前記データ構造における他のレベルの前記ブランチノード(123)のもう1つへ向けられ、前記もう1つのレベルは、少なくとも2つのレベルへと前記1レベルから分けられ、前記適合オブジェクトの前記情報データフィールドは、前記適合オブジェクトに関連した、サブエクスパンス中の前記インデックスの全てに共通した複数の前記インデックスの一部を含む、請求項1に記載のデータ構造。
【0069】(4)1つ又は複数のインデックスに関連する複数リーフノード(701)をさらに備え、ポインタフィールドは、前記データ構造の1レベルにおける前記ポインタタイプの前記適合オブジェクトの1つに関連し、前記データ構造のもう1つのレベルにおける前記リーフノードの1つへと向けられ、前記もう1つのレベルは、少なくとも2つのレベルへと前記1レベルから分けられ、前記適合オブジェクトの前記情報データフィールドは、前記1リーフノード中にある、サブエクスパンス中の前記インデックスの全てに共通した複数の前記インデックスの一部を含む、請求項1に記載のデータ構造。
【0070】(5)前記適合オブジェクトの少なくとも一部は、少なくとも1つの従属インデックスの一部を表す即時インデックスデータフィールド(702)を備え、前記従属インデックスが、更なる間接参照がなく前記コンピュータメモリ中の異なる位置へのポインタを通して即時に現れるようにする、請求項1に記載のデータ構造。
【0071】(6)トップレベルブランチ(103)から開始する複数レベルへと順序づけられたブランチノード(103,108,109,119,120,121,123)の階層を含むデータ構造を定義するステップと、前記データ構造中にインデックスを記憶するステップとを有するデータ構造中のインデックスを記憶する方法であって、前記ブランチノードの各々は、適合オブジェクト(104,105,110,112,111,114-118、図2)のアレイを備え、前記ブランチノードの各々によりマップされる前記インデックスのサブエクスパンスに関連し、前記適合オブジェクトの各々は、前記適合オブジェクトのタイプを示すタイプフィールドTを含み、前記タイプは、ポインタタイプ及び前記インデックスの少なくとも1つが前記適合オブジェクトに記憶された即時タイプ(図2−6)を含み、前記ポインタタイプには、他ノードへのポインタ(116B)及び前記他のノードについての情報を記憶する情報データフィールド(116A)を含む方法。
【0072】(7)1つ又は複数のインデックスに関連する複数リーフノード(701)をさらに含み、ポインタフィールドは、前記データ構造の1レベルの前記ポインタタイプの前記適合オブジェクトのうち1つに関連し、前記データ構造のもう1つのレベルにおける前記リーフノードの1つに向けられ、前記もう1つのレベルは、少なくとも2つのレベルへと前記1つのレベルから分けられ、前記適合オブジェクトの前記情報データフィールドは、前記1リーフノード中にある、サブエクスパンス中の前記インデックスの全てに共通した複数の前記インデックスの一部を含む、請求項6に記載の方法。
【0073】(8)前記適合オブジェクトの少なくとも一部は、少なくとも1つの従属インデックスの一部を表すよう構成された即時インデックスデータフィールド(702)を備え、前記従属インデックスが、更なる間接参照がなく前記コンピュータメモリ中の異なる位置へのポインタを通して即時に現れるようにするステップをさらに含む、請求項6に記載の方法。
【0074】(9)エラー検出データ(703)を前記適合オブジェクトに記憶するステップと、前記エラー検出データを用いて前記データ構造内のエラー状況を検出するステップとをさらに含む請求項6に記載の方法。
【0075】(10)トップレベルブランチ(103)から開始する複数レベルへと順序づけられたブランチノード(103,108,109,119,120,121,123)の階層を含む、インデックス格納のための前記メモリに記憶されたデータ構造(図1)を備え、前記ブランチノードの各々は、適合オブジェクト(104,105,110,112,111,114-118、図2)のアレイを備え、前記ブランチノードの各々によりマップされる前記インデックスのサブエクスパンスに関連し、前記適合オブジェクトの各々は、前記適合オブジェクトのタイプを示すタイプフィールド(T)を含み、前記タイプは、ポインタタイプ及び前記インデックスの少なくとも1つが前記適合オブジェクトに記憶された即時タイプ(図2−6)を含み、前記ポインタタイプには、他ノードへのポインタ(116B)及び前記他のノードについての情報を記憶する情報データフィールド(116A)を含む、データ処理システム上で実行されるアプリケーションプログラムによるアクセスのためのデータを記憶するコンピュータメモリ(803)。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013