特許

J-GLOBAL ID：200903018650731354

索引方式

発明者： 平野 泰宏 ,  三浦 史光 ,  小林 伸幸
出願人/特許権者： 日本電信電話株式会社
代理人 (1件)： 三好 秀和 (外1名)
公報種別：公開公報
出願番号（国際出願番号）：特願平5-015153
公開番号（公開出願番号）：特開平6-231172
出願日： 1993年02月02日
公開日（公表日）： 1994年08月19日
要約：

【要約】【目的】 データを挿入する時間を短縮し、プロセス間の同時走行性を高める。【構成】 キー値からハッシュ値を計算するハッシュ関数計算手段と、データの格納場所を保持するポインタまたはデータ3-2〜6-2および局所深さ3-1〜6-1を保持するバケット3〜6と、前記バケットの格納場所を保持する0番から2の整数(≧大域深さ)乗-1番までの2の整数乗個のエントリ1-2〜1-9および大域深さ1-1を持ちエントリ数を変化させうるディレクトリ1と、作業用変数2とでアクセス手段を構成し、データを検索する際にバケットの局所深さが作業変数値以下であるバケットを見つけるまでバケット探索を繰り返すことにより、バケット分割時に更新する必要のあるエントリ数を削減できるようにし、また、ディレクトリのメンテナンスを行なうことによって、バケット探索を繰り返す回数を削減できるようにしている。

請求項（抜粋）：

データを格納する記憶装置と、該記憶装置に格納されたデータのうち所望のキー値を持つデータの格納場所を調べるためのアクセス手段を具備する計算機システムにおいて、前記アクセス手段を、キー値からハッシュ値を計算するハッシュ関数計算手段と、データの格納場所を保持するポインタまたはデータおよび局所深さを保持するバケットと、前記バケットの格納場所を保持する0番から2の整数(≧大域深さ)乗-1番までの2の整数乗個のエントリおよび大域深さを持ちエントリ数を変化させうるディレクトリと、作業用変数とで構成し、所望のキー値を持つデータを検索する際には、キー値からハッシュ値を計算し、大域深さを作業用変数に代入し、ハッシュ値の下位から該作業用変数値分のビットを用いてエントリを参照し、該エントリがポイントするバケットの局所深さと該作業用変数値を比較し、該作業用変数値を越えている場合には該作業用変数値に1を加えたものを該作業用変数値の新しい値として再度上記エントリの参照を行ない、該バケットの局所深さが該作業用変数値以下の場合には該バケット内のデータを検索して所望のデータを得るようにし、また、データを挿入する際には、該データのキー値からハッシュ値を計算し、前記大域深さを作業用変数に代入し、ハッシュ値の下位から該作業用変数値分のビットを用いてエントリを参照し、該エントリがポイントするバケットの局所深さと該作業用変数値を比較し、該作業用変数値を越えている場合には該作業用変数値に1を加えたものを該作業用変数値の新しい値として再度上記エントリの参照を行ない、該バケットの局所深さが該作業用変数値以下の場合には該バケットに格納領域があれば該バケットに該データを格納し、該バケットに格納領域がなければ、該バケット内の全てのデータまたはポインタと挿入したいデータまたは該データへのポインタに関してハッシュ値の下位から該バケットの局所深さ+1ビットの値によって該データまたはポインタを2つのバケットに分割し、2つのバケットの局所深さを該バケットの局所深さ+1とし、該バケットを指していた全てのエントリを、エントリ番号の下位から該2つのバケットの局所深さビットの値と該エントリが指すバケット内のポインタが指すデータまたはデータのハッシュ値の下位から該バケットの局所深さビットの値が等しくなるように更新することを特徴とする索引方式。

IPC (2件)：

G06F 15/40 500 ,  G06F 13/00