特許
J-GLOBAL ID：200903007803822581
トリー構造に基づく機能的メモリ
発明者：
,
出願人/特許権者：
代理人 (1件)：
中村 稔 (外9名)
公報種別：公表公報
出願番号（国際出願番号）：特願2001-502006
公開番号（公開出願番号）：特表2003-501749
出願日： 2000年04月28日
公開日（公表日）： 2003年01月14日
要約：
【要約】本発明は、機能的メモリを実施する方法及びメモリ構成体に係る。メモリは、多数の異なるハイアラーキーレベルにノードを有するツリー形状ハイアラーキーより成るディレクトリ構造体として実施される。このディレクトリ構造体では、所与の第1数のエレメントをテーブルが含むノードであって巾圧縮されたノードにポインタが最初に追加される。機能的トリー構造の性能を最大にするために、個々の巾圧縮されたノードを指すポインタの追加が、ノード内のポインタの数が上記第1数より小さい所定のスレッシュホールド値に対応するまで許される。巾圧縮されたノードは、その巾圧縮されたノードに受け入れられるポインタの数が上記スレッシュホールド値を越えるや否や、親ノード(N50)及び個別の子ノード(N51・・N54)により形成されたノードのクラスターへと変換される。
請求項（抜粋）：
メモリデータがデータユニットとして記憶され、各データユニットに対して専用の記憶スペースが指定される機能的メモリを実施するための方法であって、上記メモリは、多数の異なるレベルにノードを有するツリー形状のハイアラーキーを含むディレクトリ構造として実施され、少なくとも幾つかのノードは、個々のエレメントがツリー形状ハイアラーキーにおいて下位ノードを指すポインタを含みそして個々のエレメントが空でもあるような論理的テーブルにノードが関連されるようなものであり、個々のエレメントが空である場合にエレメントの内容はゼロポインタに対応し、上記テーブルにおけるエレメントの数は2の累乗に対応し、上記ディレクトリ構造で実施されるアドレス計算は、次の段階より成り、即ち(a)ツリー形状ハイアラーキーの最上位レベルのノードにおいて、使用するサーチキーによって形成されたビットストリングから所与の数のビットを選択し、その選択されたビットから、ノードにおいて次のノードのアドレスをシークするところのサーチワードを形成し、そして上記ノードへ進み、(b)使用するサーチキーによって形成されたビットストリングにおいて選択されなかったビットから所定数のビットを選択し、そしてその選択されたビットから、アクセスされたノードにおいて下位レベルの更に別の新たなノードのアドレスをシークするところのサーチワードを形成し、そしてゼロポインタを含むエレメントに遭遇するまで又は最下位レベルのノードがアクセスされるまで上記段階(b)を繰り返し、データユニットが構造体に追加されるときには、上記アドレス計算によってデータユニットを検索できるところのポインタがノードに追加され、更に、ディレクトリ構造体において所与の第1数のエレメントをテーブルが含むところのノードにポインタが先ず追加され、これらノードは、非ゼロポインタが物理的に記憶される巾圧縮されたノードであり、そして更に、サーチワードに対応してノード内の物理的記憶位置を決定できるところのビットパターンが含まれ、上記方法は、 ノードにおけるポインタの数が、上記第1の数より小さい所定のスレッシュホールド値に対応するまで、個々の巾圧縮されたノードを指すポインタの追加を許し、そして 巾圧縮されたノードに受け入れられるポインタの数が上記スレッシュホールド値を越えるや否や、巾圧縮されたノードを、親ノード及び個別の子ノードにより構成されたノードのクラスターに変換する、という段階を含むことを特徴とする方法。
IPC (4件)：
G06F 12/00 520
, G06F 12/00 501
, G06F 17/30 419
, H04Q 3/545
G06F 12/00 520 A
, G06F 12/00 501 S
, G06F 17/30 419 A
, H04Q 3/545
5B075ND35
, 5B075NR16
, 5B082CA17
, 5B082EA05
, 5K026AA03
, 5K026AA21
, 5K026BB04
, 5K026BB08
, 5K026CC07
, 5K026GG01
