(57)【要約】【課題】データベースを構成するメモリの使用効率を格段に向上させた小容量のメモリによって構成されるようにする。【解決手段】Ｎ個のハッシュ関数f[n]を用いて前記Ｎ個の索引テーブル２[n] (n=0…N-1)にそれぞれ対応したＮ個のエントリ番号をキー値から生成することができるので、Ｎ個のエントリ番号が同値となる衝突を予め回避したうえで、外部からキーＫrが入力される度にキーを格納するバケットを選択して振り分けながら格納することができるので、従来に比して索引テーブルのメモリ使用効率を大幅に改善することができる。【選択図】  図１
2016015011.tif 000002
【特許請求の範囲】
【請求項１】
複数のキー値を格納可能な複数のキー格納位置が設けられ、互いに異なるエントリ番号にそれぞれ対応付けられたバケットを複数有するＮ（Ｎは２以上の整数）個の索引テーブルと、
前記Ｎ個の索引テーブルのそれぞれに対応した互いに異なるＮ個のハッシュ関数を備え、当該Ｎ個のハッシュ関数を用いて外部から入力されたキーのキー値に基づき前記Ｎ個の索引テーブルにそれぞれ対応したＮ個のエントリ番号を生成するエントリ番号生成部と、
前記バケットのうち前記キー格納位置に対応したレコード格納位置に当該キー値と対応するレコード値を格納するレコードテーブルと、
前記Ｎ個のエントリ番号に対応した前記Ｎ個の索引テーブルにおけるＮ個のバケットの中から前記キー値を格納するバケットを選択し、当該バケットに前記キー値を格納する索引テーブル登録部と、
前記キー値を格納したキー格納位置と対応する前記レコードテーブルの前記レコード格納位置に当該キー値と対応したレコード値を格納するレコードテーブル登録部と
を備えることを特徴とするデータベース装置。
【請求項２】
請求項１記載のデータベース装置において、
前記Ｎ個のエントリ番号に対応した前記Ｎ個の索引テーブルにおけるＮ個のバケットの中から、前記キーと一致するキー値が格納されている前記バケットを検索する索引テーブル検索部と、
前記索引テーブル検索部により検索した前記バケットにおける前記キー値が格納されたキー格納位置と対応した前記レコードテーブルの前記レコード格納位置から前記レコード値を取得するレコードテーブル検索部と
を更に備えることを特徴とするデータベース装置。
【請求項３】
請求項１記載のデータベース装置において、
前記索引テーブル登録部は、前記Ｎ個のバケットのうち既に格納されているキー値の個数であるバケット長、または前記Ｎ個のバケットのうち追加で格納可能なキー値の個数である空きバケット長に基づいて、前記Ｎ個の索引テーブルにおいて前記Ｎ個のエントリ番号に対応したＮ個のバケットの中から前記キー値の格納先となるバケットを選択する
ことを特徴とするデータベース装置。
【請求項４】
請求項１記載のデータベース装置において、
前記Ｎ個の索引テーブルは、前記索引テーブル登録部および前記索引テーブル検索部の双方から同時にアクセス可能であり、
前記レコードテーブルは、前記レコードテーブル登録部および前記レコードテーブル検索部の双方から同時にアクセス可能である
ことを特徴とするデータベース装置。
【請求項５】
請求項１記載のデータベース装置において、
前記レコードテーブルは、複数のレコード値を格納可能な複数のレコード格納位置が設けられ、互いに異なるレコードエントリ番号に対応付けられたバケットをそれぞれ複数有するＮ個のレコードテーブルである
ことを特徴とするデータベース装置。
【請求項６】
請求項１に記載のデータベース装置において、
前記索引テーブル登録部は、前記Ｎ個の索引テーブルにおける全ての前記キー格納位置に当該キー値を格納しているか否かを表すキー格納マップテーブルを参照し、前記Ｎ個の索引テーブルにおいて前記Ｎ個のエントリ番号に対応したＮ個のバケットの中から前記キー値の格納先となる前記バケットを選択する
ことを特徴とするデータベース装置。
【請求項７】
複数のキー値を格納可能な複数のキー格納位置が設けられ、互いに異なるエントリ番号にそれぞれ対応付けられたバケットを複数有するＮ（Ｎは２以上の整数）個の索引テーブルのそれぞれに対応した互いに異なるＮ個のハッシュ関数を備えたエントリ番号生成部が、当該Ｎ個のハッシュ関数を用いて外部から入力されたキーのキー値に基づき前記Ｎ個の索引テーブルにそれぞれ対応したＮ個のエントリ番号を生成するエントリ番号生成ステップと、
前記Ｎ個の索引テーブルにおいて前記Ｎ個のエントリ番号に対応したＮ個のバケットの中から索引テーブル登録部が前記キー値を格納するバケットを選択し、当該バケットに前記キー値を格納する索引テーブル登録ステップと、
レコードテーブル登録部が前記バケットにおける前記キー値を格納したキー格納位置と対応するレコードテーブルのレコード格納位置に当該キー値と対応したレコード値を格納するレコードテーブル登録ステップと
を備えることを特徴とするデータベース管理方法。
【請求項８】
コンピュータに対し、
複数のキー値を格納可能な複数のキー格納位置が設けられ、互いに異なるエントリ番号にそれぞれ対応付けられたバケットを複数有するＮ（Ｎは２以上の整数）個の索引テーブルのそれぞれに対応した互いに異なるＮ個のハッシュ関数を用いて、外部から入力されたキーのキー値に基づき前記Ｎ個の索引テーブルにそれぞれ対応したＮ個のエントリ番号を生成するエントリ番号生成ステップと、
前記Ｎ個の索引テーブルにおいて前記Ｎ個のエントリ番号に対応したＮ個のバケットの中から前記キー値を格納するバケットを選択し、当該バケットに前記キー値を格納する索引テーブル登録ステップと、
前記バケットにおける前記キー値を格納したキー格納位置と対応するレコードテーブルのレコード格納位置に当該キー値と対応したレコード値を格納するレコードテーブル登録ステップと
を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベース装置、データベース管理方法およびプログラムに関し、特に、データ容量の大きい大規模データベースからキーに対応したレコードを高スループットで取得するデータベース装置、データベース管理方法およびプログラムに関する。
【背景技術】
【０００２】
従来、通信ネットワークを構築するノードであるイーサネット（登録商標）等のＬＡＮスイッチには、回線から受信したパケットの転送先を決定するための転送データベースを有するデータベース装置が備えられている。
【０００３】
ＬＡＮスイッチでは、送信するパケットに含まれる宛先アドレス（例えばＭＡＣアドレス）をキーとして、当該パケットの転送先（通信ネットワークの回線を指定する回線ＩＤおよび送信ポートを指定する送信ポートＩＤ等）や当該パケットの廃棄有無の情報をデータベース装置の転送データベースから取得することが行われる。またＬＡＮスイッチでは、パケットの宛先アドレス値と、当該宛先アドレス値を持つパケットの転送先とを転送データベースに登録することが行われる。
【０００４】
例えば、１００[Gbps]の回線間でパケットを転送する際、ＬＡＮスイッチは、最少パケット長が６４バイトのパケットを受信する時間内に当該パケットの転送先（回線ＩＤおよび送信ポートＩＤ等）を決定する必要があるものの、その決定までの時間は僅か約６ナノ秒である。
【０００５】
したがって、ＬＡＮスイッチがパケットの転送先を決定するために許容されるクロックサイクル数は、クロック周波数が５００[MHz]の場合、１サイクルが２ナノ秒であるから僅か３サイクルとなる。
【０００６】
このような短時間で転送データベースからパケットの宛先アドレスに対する転送先の情報（以下、これを「転送先情報」と呼ぶ。）を取得するための手法として、ハッシュテーブルを用いる手法がある。この手法では、ハッシュ関数を用いてパケットの宛先アドレスをハッシュテーブルのエントリ番号に変換する。
【０００７】
ハッシュテーブルの各エントリには、エントリのエントリ番号に対応付けられる宛先アドレス値と、当該宛先アドレス値に対応するパケットの転送先情報とを格納しておく。
【０００８】
ＬＡＮスイッチは、パケットの転送先情報を取得するとき、ハッシュ関数を用いてパケットの宛先アドレスをハッシュテーブルのエントリ番号に変換し、当該エントリ番号が示す当該ハッシュテーブルのエントリに格納された宛先アドレス値と当該パケットの宛先アドレスとが一致した場合に、当該エントリに格納された転送先情報を取得する。そしてＬＡＮスイッチは、その転送先情報に基づいてパケットの転送先を決定する。
【０００９】
なお、エントリに格納された宛先アドレス値と当該パケットの宛先アドレスとが一致しない場合、ＬＡＮスイッチはパケットの転送先情報がハッシュテーブルに未登録であると認識し、当該パケットを可能性のある全ての転送先に対してブロードキャストする。
【００１０】
上述したようなハッシュテーブルを用いる手法では、異なる２個以上の宛先アドレスの各々を１つのハッシュ関数により変換したときのエントリ番号が同一値となった場合、すなわち、ハッシュ値（エントリ番号）の衝突（コリジョン）が生じた場合、これらの宛先アドレスのうち１個だけしか転送データベースに登録することはできない。
【００１１】
登録できなかった宛先アドレスを持つパケットを転送する場合、当該パケットの転送先が不明なので、ＬＡＮスイッチは当該パケットをコピーし、全ての転送先にブロードキャストすることになる。このようにパケットをコピーして全ての転送先にブロードキャストすることによって、宛先アドレスを登録できた場合には不要であった転送性能劣化や回線の混雑を招くことになる。
【００１２】
上述したような転送性能劣化や回線の混雑を回避する方法として、異なる２個以上の宛先アドレスの各々を１つのハッシュ関数により変換した各ハッシュ値（各エントリ番号）に対して最大Ｌ個（Ｌは１以上の整数）の宛先アドレス値を格納可能なバケットを索引用のハッシュテーブルの各エントリとする手法がある（例えば、非特許文献１を参照。）。
【００１３】
この手法では、宛先アドレス値とその転送先情報を転送データベースに登録する場合、宛先アドレスをハッシュ関数により変換したエントリ番号に対応するバケットの空き位置に宛先アドレス値を格納するとともに、当該宛先アドレス値の格納位置に応じて定まる転送データベース内の位置に宛先アドレス値に対応する転送先情報を格納する。
【００１４】
また、パケットの転送先を決定する場合、当該パケットの宛先アドレスからハッシュ関数を用いて変換したエントリ番号により索引用のハッシュテーブル内のバケットを指定し、当該バケットに格納されている複数の宛先アドレス値のうち、当該パケットの宛先アドレスと一致する宛先アドレス値を検索する。
【００１５】
この検索において、当該パケットの宛先アドレスと一致する宛先アドレス値が指定のバケットから見つけられた場合、ＬＡＮスイッチは宛先アドレス値の格納位置に応じた転送データベース内の位置に格納されている転送先情報を取得し、当該転送先情報を用いてパケットの転送先を決定する。
【００１６】
このように、上述した手法では、異なる２個以上の宛先アドレスの各々をハッシュ関数により変換したハッシュ値（エントリ番号）が同じになる最大Ｌ個までの宛先アドレス値を転送データベースに登録することができるため、索引用のハッシュテーブルにおけるバケットのバケットサイズＬを大きくすることにより、ハッシュ値の衝突によって宛先アドレス値を登録できない確率を低減できる。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】大久保修一，“「さくらのクラウド」を例に見るネットワーク仮想化の設計と実装”，さくらインターネット研究所，p.25-26http://research.sakura.ad.jp/wp-content/uploads/2011/10/20110927-hbstudy.pdf
【発明の概要】
【発明が解決しようとする課題】
【００１８】
しかしながら、一定個数のランダム値からなる宛先アドレスを登録することのできるデータベース装置においては、同じハッシュ値（エントリ番号）を持つことになる宛先アドレスの個数にばらつきが生じるので、一定個数の宛先アドレスを登録可能なハッシュテーブルのバケットサイズＬは、宛先アドレスの個数のばらつきの最大値とする必要がある。
【００１９】
しかしながら、同じハッシュ値（エントリ番号）を持つ宛先アドレスの個数のばらつきが最大値となる確率は低いため、一定個数の宛先アドレスを転送データベースに登録し終えた時点で、索引用のハッシュテーブル内のバケットの大多数において、そのバケットに宛先アドレス値が格納されている宛先アドレスの個数はバケットサイズＬに到達していないと考えられる。
【００２０】
すなわち、索引用のハッシュテーブルに対して設けられたメモリには、未使用領域が多く残存することになる。また、同じ理由によって、転送データベース用に設けられたメモリに対しても、多数の未使用領域が残存してしまう。
【００２１】
したがって、索引用のハッシュテーブルや転送データベースをメモリにより構成したデータベース装置においては、メモリの使用効率が低くなり、登録すべき宛先アドレスや転送先情報のデータサイズよりも大きな容量のメモリを備える必要があり、メモリの無駄が大きいという問題があった。
【００２２】
本発明は、以上のような問題点を解消するためになされたものであり、データベースを構成するメモリの使用効率を格段に向上させた小容量のメモリによって構成されるデータベース装置、データベース管理方法およびプログラムを提案することを目的とする。
【課題を解決するための手段】
【００２３】
本発明に係るデータベース装置は、複数のキー値を格納可能な複数のキー格納位置が設けられ、互いに異なるエントリ番号にそれぞれ対応付けられたバケットを複数有するＮ（Ｎは２以上の整数）個の索引テーブルと、前記Ｎ個の索引テーブルのそれぞれに対応した互いに異なるＮ個のハッシュ関数を備え、当該Ｎ個のハッシュ関数を用いて外部から入力されたキーのキー値に基づき前記Ｎ個の索引テーブルにそれぞれ対応したＮ個のエントリ番号を生成するエントリ番号生成部と、前記バケットのうち前記キー格納位置に対応したレコード格納位置に当該キー値と対応するレコード値を格納するレコードテーブルと、前記Ｎ個のエントリ番号に対応した前記Ｎ個の索引テーブルにおけるＮ個のバケットの中から前記キー値を格納するバケットを選択し、当該バケットに前記キー値を格納する索引テーブル登録部と、前記キー値を格納したキー格納位置と対応する前記レコードテーブルの前記レコード格納位置に当該キー値と対応したレコード値を格納するレコードテーブル登録部とを備えるようにする。
【００２４】
請求項１において、前記Ｎ個のエントリ番号に対応した前記Ｎ個の索引テーブルにおけるＮ個のバケットの中から、前記キーと一致するキー値が格納されている前記バケットを検索する索引テーブル検索部と、前記索引テーブル検索部により検索した前記バケットにおける前記キー値が格納されたキー格納位置と対応した前記レコードテーブルの前記レコード格納位置から前記レコード値を取得するレコードテーブル検索部とを更に備えることを特徴とする。
【００２５】
請求項１において、前記索引テーブル登録部は、前記Ｎ個のバケットのうち既に格納されているキー値の個数であるバケット長、または前記Ｎ個のバケットのうち追加で格納可能なキー値の個数である空きバケット長に基づいて、前記Ｎ個の索引テーブルにおいて前記Ｎ個のエントリ番号に対応したＮ個のバケットの中から前記キー値の格納先となるバケットを選択することを特徴とする。
【００２６】
請求項１において、前記Ｎ個の索引テーブルは、前記索引テーブル登録部および前記索引テーブル検索部の双方から同時にアクセス可能であり、前記レコードテーブルは、前記レコードテーブル登録部および前記レコードテーブル検索部の双方から同時にアクセス可能であることを特徴とする。
【００２７】
請求項１において、前記レコードテーブルは、複数のレコード値を格納可能な複数のレコード格納位置が設けられ、互いに異なるレコードエントリ番号に対応付けられたバケットをそれぞれ複数有するＮ個のレコードテーブルであることを特徴とする。
【００２８】
請求項１において、前記索引テーブル登録部は、前記Ｎ個の索引テーブルにおける全ての前記キー格納位置に当該キー値を格納しているか否かを表すキー格納マップテーブルを参照し、前記Ｎ個の索引テーブルにおいて前記Ｎ個のエントリ番号に対応したＮ個のバケットの中から前記キー値の格納先となる前記バケットを選択することを特徴とする。
【発明の効果】
【００２９】
本発明によれば、Ｎ個のハッシュ関数を用いて前記Ｎ個の索引テーブルにそれぞれ対応したＮ個のエントリ番号をキー値から生成することができるので、Ｎ個のエントリ番号が衝突する確率を予め低減し、外部からキーが入力される度にＮ個の索引テーブルの中からキーを格納すべきバケットを選択して格納することができるので、従来に比して索引テーブルのメモリ使用効率を大幅に改善するとともに、少容量のメモリによって構成することができる。
【図面の簡単な説明】
【００３０】
【図１】第１の実施の形態におけるデータベース装置の構成を示すブロック図である。
【図２】第１の実施の形態における索引テーブルの構成を示す図である。
【図３】第１の実施の形態におけるレコードテーブルの構成を示す図である。
【図４】第１の実施の形態における索引テーブル制御部による登録処理手順を示すフローチャートである。
【図５】第１の実施の形態における索引テーブル制御部による検索処理手順を示すフローチャートである。
【図６】第１の実施の形態におけるメモリ使用効率の説明に供するグラフである。
【図７】第２の実施の形態におけるデータベース装置の構成を示すブロック図である。
【図８】第３の実施の形態におけるデータベース装置の構成を示すブロック図である。
【図９】第３の実施の形態におけるレコードテーブルの構成を示す図である。
【図１０】第３の実施の形態におけるキー格納マップテーブルの構成を示す図である。
【図１１】第３の実施の形態における索引テーブル登録部による登録処理手順を示すフローチャートである。
【図１２】第３の実施の形態における索引テーブル検索部による検索処理手順を示すフローチャートである。
【発明を実施するための形態】
【００３１】
＜第１の実施の形態＞
＜データベース装置の全体構成＞
以下、本発明における第１の実施の形態におけるデータベース装置の構成について図１を用いて説明する。
【００３２】
このデータベース装置１は、ＣＰＵ(Central Processing Unit)、メモリ、インタフェース等からなるコンピュータ（ハードウェア）にコンピュータプログラム（ソフトウェア）をインストールすることによって実現され、当該データベース装置１の機能は、コンピュータの各種ハードウェア資源とコンピュータプログラムとが協働することによって実現される。また、コンピュータプログラムは、コンピュータ読取可能な記録媒体や記憶装置に格納された状態で提供されても良く、或いは電気通信回線を介して提供されても良い。
【００３３】
図１に示すように、第１の実施の形態におけるデータベース装置１は、複数のキーに対応したキー値（宛先アドレス値）を格納するＮ個（Ｎは２以上の整数）の索引テーブル２[n](n=0…N-1)、索引テーブル２[n]に格納された複数のキー値（宛先アドレス値）にそれぞれ対応した複数のレコード値（転送先情報）を格納するレコードテーブル３、索引テーブル２[n]に対するキー値（宛先アドレス値）の登録や検索、レコードテーブル制御部５と連動してキー値に対応したレコード値のレコードテーブル３に対する登録やレコードテーブル３からの検索を制御する索引テーブル制御部４、索引テーブル制御部４と連動してレコードテーブル３に対するレコード値の登録またはレコードテーブル３からのレコード値の検索を制御するレコードテーブル制御部５によって構成されている。なお、データベース装置１では、複数の索引テーブル２[n] (n=0…N-1)およびレコードテーブル３によって転送データベースが構成されている。
【００３４】
＜索引テーブルの構成＞
図２には、索引テーブル２[n] (n=0…N-1)の構成例を示す。索引テーブル２[0]、……、２[n]、……、２[N-1]は全て同じ構成であるため、ここでは便宜上、索引テーブル２[n]について説明する。
【００３５】
索引テーブル２[n] (n=0…N-1)はメモリであり、各索引テーブル２[n]はＭ個のエントリ１１[i](i=0…M-1)を有している。ここで、[n] (n=0…N-1)は索引テーブル２[n]を特定する索引テーブル番号（２以上の整数）であり、[i] (i=0…M-1)は索引テーブル２[n]内の複数のエントリ１１[i]を特定するエントリ番号（１以上の整数）である。
【００３６】
このエントリ１１[i](i=0…M-1)は、複数のキー値（宛先アドレス値）を格納可能なＬ個のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)が設けられたバケット１０[i](i=0…M-1)として構成されている。この場合、エントリ１１[i]はバケット１０[i]であると言え、[i]はエントリ番号であると同時にバケット番号（１以上の整数）であるとも言える。
【００３７】
ここで、索引テーブル２[n] (n=0…N-1)のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)は、エントリ番号[i] (i=0…M-1)と、バケット内キー格納位置番号[j](j=0…L-1)とによって特定される。バケット内キー格納位置番号[j] (j=0…L-1)は、バケット１０[i] (i=0…M-1)内のキー格納位置を特定する番号（１以上の整数）である。
【００３８】
このような構成の索引テーブル２[n](n=0…N-1)に格納されたキー値（宛先アドレス値）を読み出す場合には、索引テーブル２[n] (n=0…N-1)を特定する索引テーブル番号[n]を指定し、さらに、読み出すべきエントリ１１[i]を特定するエントリ番号[i]（バケット番号[i]）を指定することにより当該エントリ１１[i]（バケット１０[i]）に格納された複数のキー値（宛先アドレス）に対する読出アクセスを行う（詳細については後述する）。
【００３９】
また、索引テーブル２[n] (n=0…N-1)に対して、新たなキーに対応したキー値（宛先アドレス値）を格納する場合には、格納先となる索引テーブル２[n] (n=0…N-1)を特定する索引テーブル番号[n] (n=0…N-1)を指定する。そして、エントリ１１[i] (i=0…M-1)を特定するエントリ番号[i]（バケット番号[i]）およびバケット内キー格納位置番号[j](j=0…L-1)を指定することにより、キー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)を特定し、そのキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に対して格納すべきキー値（宛先アドレス値）の書込アクセスを行う（詳細については後述する）。
【００４０】
＜レコードテーブルの構成＞
図３には、レコードテーブル３の構成例を示す。レコードテーブル３はメモリであり、全ての索引テーブル２[n](n=0…N-1)のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に格納したキー値（宛先アドレス値）の各々に対応したレコード値（パケットの転送先情報）を格納可能なレコードエントリ２０[k](k=0…K-1)が設けられている。
【００４１】
ここで、[k] (k=0…K-1)は、レコードテーブル３内のレコード格納位置であるレコードエントリ２０[k]を特定するレコードエントリ番号（１以上の整数）であり、索引テーブル２[n] (n=0…N-1)のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に格納されたキー値に対応したレコード値の格納位置を特定するためのものである。
【００４２】
第１の実施の形態において、全ての索引テーブル２[n](n=0…N-1)に設けられたキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)の全個数は、索引テーブル数Ｎ×各索引テーブル２[n] (n=0…N-1)のテーブルサイズＭ（索引テーブル２[n]のエントリ数（バケット数））×各バケットのバケットサイズＬ（キー格納位置１２[i][j]の個数）により表される。
【００４３】
したがって、レコードテーブル３の各レコードエントリ２０[k] (k=0…K-1)に１個のレコード値（パケットの転送先情報）を格納する１個のメモリとして構成した場合のレコードテーブル３のレコードテーブルサイズＫは、Ｋ＝Ｎ×Ｍ×Ｌとなり、全ての索引テーブル２[n] (n=0…N-1)に設けられたキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)の全個数と同じになる。
【００４４】
索引テーブル２[n] (n=0…N-1)のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)と、レコードテーブル３のレコードエントリ２０[k] (k=0…K-1)のレコードエントリ番号[k]との対応付けは、当該キー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に基づいてレコードエントリ２０[k] (k=0…K-1)のレコードエントリ番号[k]を一意に算出できる計算方法であればよい。
【００４５】
例えば、１つの計算方法として、索引テーブル２[n] (n=0…N-1)を示す索引テーブル番号[n]、エントリ１１[i]を示すエントリ番号[i] (i=0…M-1)、キー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)を示すバケット内キー格納位置番号[j](j=0…L-1)を用いて、レコードエントリ２０[k] (k=0…K-1)のレコードエントリ番号[k]を次の（式１）により算出することが可能である。
k=n×M×L＋i×L＋j …………………………………………………………（式１）
【００４６】
このような構成のレコードテーブル３のレコードエントリ２０[k] (k=0…K-1)に格納されたレコード値（転送先情報）をデータベース装置１が読み出す場合、当該データベース装置１は読出先となるレコードエントリ２０[k] (k=0…K-1)に対応したレコードエントリ番号[k]を指定することにより読出アクセスを行う（詳細については後述する）。
【００４７】
一方、レコードテーブル３に対して新たなレコード値（転送先情報）を格納する場合、データベース装置１は格納先となるレコードエントリ番号[k] (k=0…K-1)を指定することにより書込アクセスを行う（詳細については後述する）。
【００４８】
＜索引テーブル制御部の構成＞
図１において、索引テーブル登録部および索引テーブル検索部としての索引テーブル制御部４は、外部から入力された登録用のキーＫr（パケットの宛先アドレス）のキー値（宛先アドレス値）を索引テーブル２[n] (n=0…N-1)のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に格納したり、当該キー値に対応した登録対象のレコードＲrのレコード値（転送先情報）をレコードテーブル３に格納する等の制御をレコードテーブル制御部５と連動して行うものである。
【００４９】
また、索引テーブル制御部４は、外部から入力された検索用のキーＫsに対応した検索対象のレコードＲsのレコード値をレコードテーブル３から取得する等の制御についてもレコードテーブル制御部５と連動して行うものである。
【００５０】
索引テーブル制御部４は、Ｎ個の索引テーブル２[n] (n=0…N-1)にそれぞれ対応した互いに異なるＮ個のハッシュ関数f[n] (n=0…N-1)を備えるとともに、登録用のキーＫr（宛先アドレス）から当該Ｎ個のハッシュ関数ｆ[n] (n=0…N-1)にそれぞれ対応したハッシュ値からなるエントリ番号[n] (n=0…N-1)を生成するエントリ番号生成部４ａを有している。
【００５１】
ここで、エントリ番号[n] (n=0…N-1)は、ハッシュ関数f[n] (n=0…N-1)に対応してキーＫrから変換されるものであり、各索引テーブル２[n](n=0…N-1)に設けられた複数のエントリ１１[i] (i=0…M-1)に対応する。
【００５２】
索引テーブル制御部４は、登録用のキーＫrのキー値（宛先アドレス値）を索引テーブル２[n] (n=0…N-1)に格納する際、キー値が未格納のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)を探索し、そこに格納する必要がある。
【００５３】
そのため、索引テーブル制御部４では、各索引テーブル２[n] (n=0…N-1)のうち、キーＫrをハッシュ関数f[n] (n=0…N-1)により変換したエントリ番号[n] (n=0…N-1)のバケット１０[n] (n=0…N-1)について、バケット長（後述する）もしくは空きバケット長（後述する）を取得する必要がある。
【００５４】
ここで、バケット長とは、エントリ番号[n] (n=0…N-1)のバケット１０[n] (n=0…N-1)における複数のキー格納位置１２[i][j](i=0…M-1)(j=0…L-1)に既に格納されているキー値の個数である。また、空きバケット長とは、エントリ番号[n] (n=0…N-1)のバケット１０[n] (n=0…N-1)における複数のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に対して追加で格納可能なキー値の個数である。
【００５５】
索引テーブル制御部４において、エントリ番号[n] (n=0…N-1)のバケット１０[n] (n=0…N-1)におけるバケット長または空きバケット長を取得する方法としては、以下の３通りがある。
【００５６】
一つ目のバケット長取得方法では、索引テーブル２[n] (n=0…N-1)のうち、キー値（宛先アドレス値）が未格納の全ての各キー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に対して、無効なキー値（格納済のキー値とは一致しない任意の値）を格納しておく。これにより、索引テーブル制御部４は、バケット長もしくは空きバケット長を取得する場合に、エントリ番号[n] (n=0…N-1)により指定したバケット１０[n] (n=0…N-1)における全キー値（有効なキー値および無効なキー値の全て）を取得し、当該全キー値のうち、無効なキー値を持つキーＫrの個数を計数し、それを対象となるバケット１０[n](n=0…N-1)に対する空きバケット長として取得することができる。ただし、索引テーブル制御部４は有効なキー値を持つキーＫrの個数を計数してもよく、この場合には、それを対象となるバケット１０[n] (n=0…N-1)に対するバケット長として取得することができる。
【００５７】
二つ目のバケット長取得方法では、索引テーブル２[n] (n=0…N-1)における全てのキー格納位置１２[i][j](i=0…M-1)(j=0…L-1)に対して格納有無を表すフラグを設け、初期状態（未だ登録されたキー値が存在しない状態）において当該フラグをクリアしておき、キー値の格納に合わせてキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に設けられたフラグをセットする。これにより、索引テーブル制御部４は、バケット長もしくは空きバケット長を取得する場合に、エントリ番号[n] (n=0…N-1)により指定した対象となるバケット１０[n] (n=0…N-1)のキー格納位置１２[i][j](i=0…M-1)(j=0…L-1)にセットされたフラグ（あるいはセットされていないフラグ）の個数を計数し、それを対象となるバケット１０[n] (n=0…N-1)に対するバケット長（あるいは空きバケット長）として取得することができる。
【００５８】
三つ目のバケット長取得方法では、索引テーブル２[n] (n=0…N-1)の各エントリ１１[n] (n=0…N-1)に対してバケット長（あるいは空きバケット長）を表すカウンタを設け、初期状態（未だ登録されたキー値が存在しない状態）において当該カウンタを初期化しておき、キー値の格納に合わせて当該キー値を格納したバケット１０[n] (n=0…N-1)に対応するカウンタのカウント値を更新する。これにより、索引テーブル制御部４は、バケット長もしくは空きバケット長を取得する場合に、各エントリ１１[n] (n=0…N-1)のカウンタ値を取得し、そのカウンタ値を対象となるバケット１０[n] (n=0…N-1)に対するバケット長（あるいは空きバケット長）として取得することができる。
【００５９】
＜レコードテーブル制御部の構成＞
図１において、レコードテーブル登録部およびレコードテーブル検索部としてのレコードテーブル制御部５は、索引テーブル制御部４と連動して、索引テーブル２[n] (n=0…N-1)のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に格納した登録用のキーＫrのキー値（宛先アドレス値）に対応した登録対象のレコードＲrのレコード値（転送先情報）をレコードテーブル３に格納する制御を行うものである。
【００６０】
またレコードテーブル制御部５は、索引テーブル制御部４と連動して、当該索引テーブル制御部４に入力された検索用のキーＫsに対応する検索対象のレコードＲsをレコードテーブル３から取得するための制御を行うものである。
【００６１】
ここで、登録用のキーＫrと検索用のキーＫsとは異なるキー値であることを前提としているが、登録用および検索用の双方において同じキー値のキーＫrまたはＫsが用いられてもよい。同様に、登録対象のレコードＲrと検索対象のレコードＲsとは異なるレコード値であることを前提としているが、登録対象および検索対象のレコードＲrおよびＲsに対して同じレコード値が用いられてもよい。
【００６２】
＜登録用のキーおよび当該キーに対応したレコードの登録処理手順＞
次に、データベース装置１における登録用のキーＫrおよび当該キーＫrに対応した登録対称のレコードＲrの転送データベースに対する登録処理について説明する。なお、索引テーブル制御部４によるキーＫrの転送データベースに対する登録動作については、図４のフローチャートを参照しながら説明する。
【００６３】
データベース装置１（図１）では、登録用のキーＫr（宛先アドレス）と当該キーＫrに対応する登録対象のレコードＲr（転送先情報）を転送データベースに登録する場合、索引テーブル制御部４は、外部から登録用のキーＫrと登録命令を意味する制御信号Ｓ１とを入力する（ステップＳＰ１）。
【００６４】
索引テーブル制御部４は、各索引テーブル２[n](n=0…N-1)にそれぞれ対応したＮ個のハッシュ関数ｆ[n] (n=0…N-1)を用いて、外部から入力した登録用のキーＫr（宛先アドレス）からＮ個のエントリ番号[n] (n=0…N-1)を同時に生成する（ステップＳＰ２[0]、……、ステップＳＰ２[n]、……、ステップＳＰ２[N-1]）。
【００６５】
索引テーブル制御部４は、各エントリ番号[n] (n=0…N-1)の各バケット１０[n] (n=0…N-1)に対し、既にキー値が格納されている場合の個数を表す各バケット長[n] (n=0…N-1) を取得する（ステップＳＰ３[0]、……、ステップＳＰ３[n]、……、ステップＳＰ３[N-1]）。なお、バケット長[n]を取得する代わりに、追加で格納可能なキー値の個数である空きバケット長[n]を取得するようにしてもよい。
【００６６】
索引テーブル制御部４は、ステップＳＰ３[0]、……、ステップＳＰ３[n]、……、ステップＳＰ３[N-1]により得られたＮ個のバケット長[n](n=0…N-1)の中から最小値となるバケット長[nr]を探索し、その最小値のバケット長[nr]に対応した索引テーブル２[nr]を選択する（ステップＳＰ４）。
【００６７】
索引テーブル制御部４は、最小値のバケット長[nr]に対応した索引テーブル２[nr]のキー格納位置[nr][j] (j=0…L-1)のうち、キー値が未格納のキー格納位置１２[nr][jr]を探索する（ステップＳＰ５）。ここで、キー格納位置１２[nr][jr] における[nr]は、キー格納位置１２を特定する最小値のバケット長[nr]に対応したエントリ番号[nr]であり、[jr]はキー値が未格納のキー格納位置を特定するバケット内キー格納位置番号[jr]である。
【００６８】
索引テーブル制御部４は、索引テーブル２[nr]におけるエントリ１１[nr]のバケット１０[nr]のうち、キー値が未格納のキー格納位置１２[nr][jr]を見つけられたか否かを判定し（ステップＳＰ６）、見つけられた場合には、索引テーブル２[nr]におけるエントリ１１[nr]のバケット１０[nr]においてキー値が未格納のキー格納位置１２[nr][jr]に登録用のキーＫrのキー値を格納する（ステップＳＰ７）。
【００６９】
索引テーブル制御部４は、索引テーブル２[nr]のキー格納位置１２[nr][jr]に対して登録用のキーＫrのキー値を格納したので、索引テーブル２[nr]を示す索引テーブル番号[nr]、エントリ番号[nr]、キー格納位置１２[nr][jr]を示すバケット内キー格納位置番号[jr]を上述した（式１）に代入する。
【００７０】
これにより索引テーブル制御部４は、レコードエントリ２０[k]のレコードエントリ番号[k] (k=0…K-1)を次の（式２）により算出し、これをレコードテーブル制御部５に供給し（ステップＳＰ８）、索引テーブル制御部４の登録処理を終了する。
k＝索引テーブル番号[nr]×M×L＋エントリ番号[nr]×L＋jr………………（式２）
【００７１】
レコードテーブル制御部５（図１）は、索引テーブル制御部４と同様に外部から登録命令を意味する制御信号Ｓ１が入力されており、索引テーブル制御部４から供給されたレコードテーブル３のレコードエントリ番号[k] (k=0…K-1)と、登録用のキーＫrに対応した登録対象のレコードＲrとを入力する。
【００７２】
レコードテーブル制御部５は、登録命令を意味する制御信号Ｓ１にしたがって、レコードエントリ番号[k] (k=0…K-1)に対応したレコードテーブル３のレコードエントリ２０[k]にレコードＲrのレコード値を格納する。
【００７３】
ところで、索引テーブル制御部４は、索引テーブル２[nr]におけるエントリ１１[nr]のバケット１０[nr]のうち、キー値が未格納のキー格納位置１２[nr][jr]を見つけられなかった場合、すなわちエントリ１１[nr]のバケット[nr]に既にキー値が全て格納されている場合には、登録用のキーＫrのキー値を索引テーブル２[nr]に登録することはできないので、登録不可時の処理を行う（ステップＳＰ７）。
【００７４】
索引テーブル制御部４は、登録不可時の処理として、例えば、登録用のキーＫrのキー値を索引テーブル２[nr]に登録できない回数をカウンタにより計数し、計数する度に更新し、その計数値を保持しておく。
【００７５】
あるいは索引テーブル制御部４は、登録不可時の処理として、索引テーブル２[nr]におけるエントリ１１[nr]のバケット[nr]に対して既に格納済のキー値のうち１個のキー値の登録を抹消する。そして索引テーブル制御部４は、その抹消したキー格納位置１２[i][r] (i=0…M-1) (j=0…L-1)に対して登録用のキーＫrのキー値を登録するとともに、そのキー格納位置１２[i][r] (i=0…M-1) (j=0…L-1)に対応したレコードテーブル３のレコードエントリ番号[k] (k=0…K-1)を算出し、これをレコードテーブル制御部５へ供給する。
【００７６】
なお、索引テーブル制御部４は、バケット長[n](n=0…N-1)が最小値となるバケット長[nr]のエントリ番号[nr]に対応する索引テーブル２[nr]を選択するようにしたが（ステップＳＰ４）、これに限るものではなく、登録対象とすべき索引テーブル２[nr]を選択する索引テーブル選択方法としては、それ以外に以下の３通りがある。
【００７７】
一つ目の索引テーブル選択方法では、空きバケット長[n] (n=0…N-1)が０よりも大きいバケット１０[n] (n=0…N-1)の中で索引テーブル番号[n] (n=0…N-1)が最小値の索引テーブル番号[nr]を持つ索引テーブル２[nr]を選択する。
【００７８】
二つ目の索引テーブル選択方法では、空きバケット長[n] (n=0…N-1)の中で最大値をとる空きバケット長[nr] となった索引テーブル番号[nr]を持つ索引テーブル２[nr]を選択する。
【００７９】
三つ目の索引テーブル選択方法では、各索引テーブル２[n] (n=0…N-1)が異なるテーブルサイズＭ（エントリ１１[i] (i=0…M-1) の個数）である場合に、空きバケット長[n] (n=0…N-1)を索引テーブル２[n] (n=0…N-1)毎に設定された重み係数で重み付けした重み付け空きバケット長[n] (n=0…N-1)のうち、最大値をとる重み付け空きバケット長[nr]となった索引テーブル番号[nr]を持つ索引テーブル２[nr]を選択する。
【００８０】
なお、一つ目乃至三つ目の索引テーブル選択方法においては、各索引テーブル２[n] (n=0…N-1)のバケットサイズＬ（キー格納位置１２[i][r] (i=0…M-1) (j=0…L-1)の個数）が異なる場合にも適用することができる。
【００８１】
＜検索用のキーに対応したレコードの検索処理手順＞
次に、データベース装置１において、検索用のキーＫsのキー値に対応した検索対象となるレコードＲsのレコード値を転送データベースから検索する検索処理について説明する。なお、索引テーブル制御部４により検索用のキーＫsに対応したレコードＲsを転送データベースから検索する検索動作については、図５のフローチャートを参照しながら説明する。
【００８２】
データベース装置１では、検索用のキーＫsに対応したキー値（宛先アドレス）に対応したレコードＲsのレコード値（転送先情報）を転送データベースから取得する場合、索引テーブル制御部４は、当該キーＫs（宛先アドレス）と、検索命令であることを示す制御信号Ｓ２とを入力する（ステップＳＰ１１）。
【００８３】
索引テーブル制御部４は、全索引テーブル２[n](n=0…N-1)にそれぞれ対応したＮ個のハッシュ関数ｆ[n] (n=0…N-1)を用いて、外部から入力した検索用のキーＫs（宛先アドレス）からＮ個のエントリ番号[n] (n=0…N-1)を同時に生成する（ステップＳＰ１２[0]、……、ステップＳＰ１２[n]、……、ステップＳＰ１２[N-1]）。
【００８４】
索引テーブル制御部４は、索引テーブル２[n](n=0…N-1)における各エントリ番号[n] (n=0…N-1)の各バケット１０[n] (n=0…N-1)に既に格納されている最大Ｌ個のキー値（宛先アドレス値）を取得する（ステップＳＰ１３[0]、……、ステップＳＰ１３[n]、……、ステップＳＰ１３[N-1]）。
【００８５】
索引テーブル制御部４は、ステップＳＰ１３[0]、……、ステップＳＰ１３[n]、……、ステップＳＰ１３[N-1]によりそれぞれ取得した最大Ｌ個のキー値（宛先アドレス値）のうち、検索用のキーＫs（宛先アドレス）と一致するキー値（宛先アドレス値）が格納されている索引テーブル番号[ns]と、そのキー格納位置[ns][js]とを探索する（ステップＳ１４）。
【００８６】
ここで、キー格納位置１２[ns][js] における[ns]は、検索用のキーＫs（宛先アドレス）と一致するキー値（宛先アドレス値）が格納されていた索引テーブル番号[ns]であり、[js]はその索引テーブル番号[ns]の索引テーブル２[ns]のうち、検索用のキーＫs（宛先アドレス）と一致するキー値（宛先アドレス値）が格納されていたキー格納位置を特定するバケット内キー格納位置番号[js]である。
【００８７】
索引テーブル制御部４は、検索用のキーＫs（宛先アドレス）と一致するキー値（宛先アドレス値）を索引テーブル番号[ns]の索引テーブル２[ns]の中から見つけられたか否かを判定し（ステップＳＰ１５）、見つけられた場合には、索引テーブル２[ns]を示す索引テーブル番号[ns]、エントリ番号[ns]、キー格納位置１２[ns][js]を示すバケット内キー格納位置番号[js]を上述した（式１）に代入する。
【００８８】
これにより索引テーブル制御部４は、レコードエントリ２０[k]のレコードエントリ番号[k] (k=0…K-1)を次の（式３）により算出し、これをレコードテーブル制御部５に供給し（ステップＳＰ１６）、索引テーブル制御部４の検索処理を終了する。
k＝索引テーブル番号[ns]×M×L＋エントリ番号[ns]×L＋js………………（式３）
【００８９】
レコードテーブル制御部５（図１）は、索引テーブル制御部４と同様に外部から検索命令を意味する制御信号Ｓ２が既に入力されており、その状態で索引テーブル制御部４から供給されたレコードテーブル３のレコードエントリ番号[k]を入力する。
【００９０】
レコードテーブル制御部５は、検索命令を意味する制御信号Ｓ２にしたがって、レコードエントリ番号[k] (k=0…K-1)に対応したレコードテーブル３のレコードエントリ２０[k] (k=0…K-1)から検索対象となるレコードＲsのレコード値を取得し、これを外部へ出力する。
【００９１】
ところで、索引テーブル制御部４は、検索用のキーＫs（宛先アドレス）と一致するキー値（宛先アドレス値）を索引テーブル番号[ns]の索引テーブル２[ns]の中から見つけられなかった場合、検索用のキーＫsのキー値は索引テーブル２[n]に未登録であるので、見つけられなかったことを表したレコード値を出力するといった検索不可時の処理を行う（ステップＳＰ１７）。
【００９２】
索引テーブル制御部４は、ステップＳＰ１７における検索不可時の他の処理として、例えば、未登録となった検索用のキーＫs（以下、これを「未登録検索キーＫs」と呼ぶ。）の検索回数をカウンタにより計数し、計数する度に更新し、その計数値を保持しておくもできる。
【００９３】
あるいは索引テーブル制御部４は、ステップＳＰ１７における検索不可時の他の処理として、未登録となった検索用のキーＫsに対するデフォルトのレコード値をレコードテーブル３から取得するため、索引テーブル２[ns]には登録済のレコード値が無いことを意味する特別なレコードエントリ番号[k] (k=0…K-1)を生成し、これをレコードテーブル制御部５へ供給することもできる。
【００９４】
＜第１の実施の形態における効果＞
第１の実施の形態におけるデータベース装置１と、既存技術を用いた従来のデータベース装置とをメモリ使用効率の観点から比較検討する。
【００９５】
例えば、第１の実施の形態におけるデータベース装置１における索引テーブル２[n]の個数Ｎを「２」、各索引テーブル２[n](n=1,2)のテーブルサイズＭ（エントリ数すなわちバケット数）を「５１２」に固定する。また、各索引テーブル２[n](n=1,2)のバケットサイズＬ（キー格納位置[i][j] (i=0…M-1) (j=0…L-1)の個数）は全て同値とし、合計バケットサイズを「Ｌ×２」とする。
【００９６】
この合計バケットサイズである「Ｌ×２」をパラメータとして、一定個数のランダム値からなる登録用のキーＫrを全て転送データベースに登録するために必要なバケットサイズＬをシミュレーションにより求めた。
【００９７】
具体的には、１６０００個のランダム値からなる登録用のキーＫrを転送データベースに登録する場合を多数回試行し、各試行において、登録できなかったキーＫrが発生したか否かを判定した。さらに、登録できなかったキーＫrが発生した試行回数をカウンタにより計数し（上述したステップＳＰ９における登録不可時の処理）、その計数値を全試行回数で除算した値を登録失敗発生率として取得した。
【００９８】
なお、第１の実施の形態では、索引テーブル２[n]の個数Ｎが「２」であるため、２個の索引テーブル２[n](n=1,2)における各々のエントリ番号[n]を生成するための２個のハッシュ関数f[n] (n=1,2)が必要となる。これら２個のハッシュ関数f[n]としては、１つのキー値から互いに相関のないエントリ番号[n]を生成できる関数を採用する。
【００９９】
例えば、キー値に対してＣＲＣ(Cyclic Redundancy Check)演算を施したビット列を２分割してエントリ番号[n]に用いたり、異なる２個のＩＶ(Initial Vector)を用いてキー値に暗号演算を施した２個のビット列をエントリ番号[n]に用いる等の方法がある。
【０１００】
比較対象とする既存技術を用いたデータベース装置では、１個の索引テーブル２[n]を有し、その索引テーブル２[n]のテーブルサイズＭを第１の実施の形態におけるデータベース装置１と同じ「５１２」に固定する。また、１個の索引テーブル２[n]の合計バケットサイズ（この場合、索引テーブル２[n]が１個なので合計バケットサイズ＝バケットサイズである）をパラメータとして、一定個数のランダム値からなる登録用のキーＫrを全て転送データベースに登録するために必要なバケットサイズＬをシミュレーションにより求めた。
【０１０１】
第１の実施の形態におけるデータベース装置１と、既存技術を用いた従来のデータベース装置とを、バケットサイズが同じ条件で比較することによって、２つのデータベース装置で使用されるメモリは同量となる。すなわち、第１の実施の形態におけるデータベース装置１における索引テーブル２[n](n=1,2)が２個で各バケットサイズ「Ｌ」のとき、比較対象とすべき従来のデータベース装置における索引テーブル２[n]は１個でバケットサイズ「Ｌ×２」となる。
【０１０２】
ここで、第１の実施の形態におけるデータベース装置１および従来のデータベース装置のテーブルサイズＭは同値であるため、合計バケットサイズが同値である場合は、索引テーブル２[n]およびレコードテーブル３に使用されるメモリ量は、両者ともに、Ｍ×Ｌ×２×「キー値１個をレコードテーブル３に格納するために必要なメモリ量」であって同値となる。
【０１０３】
したがって、第１の実施の形態におけるデータベース装置１と従来のデータベース装置との間で比較したとき、上述した登録失敗発生率が「０」となるときの合計バケットサイズの小さい方が、同じ個数のキーＫrのキー値を登録するために必要なメモリ量が小さくなり、メモリ使用効率が高いということになる。
【０１０４】
図６に、登録失敗発生率が「０」となるときの合計バケットサイズの小さい方がメモリ使用効率の高いことのシミュレーション結果を示す。第１の実施の形態におけるデータベース装置１では、合計バケットサイズ「２×Ｌ」が３６以上のときに登録失敗発生率が０となったのに対し、従来のデータベース装置では合計バケットサイズ「Ｌ」が５８以上のときに登録失敗発生率が０となった。
【０１０５】
すなわち、１６０００個のキーＫｒを登録するために、第１の実施の形態におけるデータベース装置１に必要なメモリ量が、５１２（テーブルサイズＭ）×３６（バケットサイズ）×（キー値のキー長＋レコード値のレコード長）であるのに対し、従来のデータベース装置では５１２（テーブルサイズＭ）×５８（バケットサイズ）×（キー値のキー長＋レコード値のレコード長）となる。
【０１０６】
したがって、第１の実施の形態におけるデータベース装置１では、転送データベースに必要なメモリ量を３８％（１−（３６／５８））も削減することができたことになる。また、第１の実施の形態におけるデータベース装置１では、最大５１２×３６個のキーＫrを登録できるメモリに１６０００個のキーＫｒを登録しているので、そのメモリ使用効率は８７％（１６０００／(５１２×３６)）であるのに対し、従来のデータベース装置では最大５１２×５８個のキーＫｒを登録できるメモリに１６０００個のキーＫｒを登録しているので、そのメモリ使用効率は５４％（１６０００／(５１２×５８)）である。
【０１０７】
ところで従来のデータベース装置では、索引テーブル２[n]が１個であり、１種類のハッシュ関数ｆ[n](n=0)により登録用のキーＫrを当該索引テーブル２[n]のエントリ番号[n]に変換するだけである。このため、従来のデータベース装置では、複数のハッシュ関数ｆ[n])(n=0…N-1)を用いる場合に比べて、異なるキーＫrであっても同じハッシュ値のエントリ番号に変換される確率が高い。したがって、従来のデータベース装置では、同じエントリ番号のバケットに最大Ｌ個（例えば少なくとも５８個）までのキー値を格納できるメモリ容量が必要になる。
【０１０８】
これに対して、第１の実施の形態におけるデータベース装置１では、索引テーブル制御部４がＮ個の索引テーブル２[n] (n=0…N-1)にそれぞれ対応したＮ個のハッシュ関数f[n] (n=0…N-1)を有し、登録用のキーＫrをＮ個のハッシュ関数f[n] (n=0…N-1)により索引テーブル２[n] (n=0…N-1)毎に互いに相関のないエントリ番号[n]を生成できるので、これらのエントリ番号[n]が同じハッシュ値となる確率は非常に低くなる。
【０１０９】
したがって、データベース装置１では、同じエントリ番号[n]のバケット１０[n]に対して格納するキー値の個数が少なくなる。そしてデータベース装置１では、バケット長[nr]が最小値のバケット[nr]から順番に当該キー値を格納していくことにより、索引テーブル２[n]間において格納されているキー値の個数にばらつきが少なく平坦化されるので、同じエントリ番号[n]のバケット１０[n]に格納するキー値のメモリ容量は少なくて済む。
【０１１０】
このように、データベース装置１では、Ｎ個の索引テーブル２[n] (n=0…N-1) にそれぞれ対応したＮ個のハッシュ関数f[n] (n=0…N-1)により登録用のキーＫrをＮ個のエントリ番号[n] (n=0…N-1)に同時に変換し、その各エントリ番号[n] (n=0…N-1)の各バケット１０[n]に対して当該キーＫrに対応したキー値を登録する。これにより、索引テーブル２[n] (n=0…N-1)およびレコードテーブル３のメモリ使用効率を大幅に改善することが可能であり、一定数の登録用のキーＫrを格納するために必要な索引テーブル２[n] (n=0…N-1)およびレコードテーブル３に必要なメモリ量を大幅に削減することができるという優れた効果を得ることができる。
【０１１１】
＜第１の実施の形態に対応した他の実施の形態＞
なお、レコードテーブル３は、上述した構成に限るものではなく、図１に示したようなＮ個の索引テーブル２[n]と同様に、Ｎ個のメモリからなるレコードテーブル３[n](n=0…N-1)として構成してもよい。この場合、各レコードテーブル３[n] (n=0…N-1)のテーブルサイズｋは、索引テーブル２[n]のテーブルサイズＭ（索引テーブルのエントリ数（バケット数））×各バケットのバケットサイズＬ（キー格納位置[i][j] (i=0…M-1) (j=0…L-1)の個数）となる。
【０１１２】
また、索引テーブル２[n]に格納したキー値と対応するレコード値は、索引テーブル番号[n] (n=0…N-1)、エントリ番号[i] (i=0…M-1)、バケット内キー格納位置番号[j] (j=0…L-1)を用いて、レコードテーブル３[n]のレコードエントリ番号[k]（k＝（i×L＋j）により特定されるレコードエントリ２０[k] (k=0…K-1)に格納される。
【０１１３】
このようにＮ個のメモリからなるＮ個のレコードテーブル３[n](n=0…N-1)を用いることにより、複数のキー値にそれぞれ対応した各レコード値にアクセスするとき、各キー値の格納された索引テーブル２[n]が異なっているのであれば、各レコード値の格納されたレコードテーブル３[n]すなわちメモリも異なることになる。このため、データベース装置１は各レコード値に対して同時並行的にアクセスすることが可能となり、各キー値のアクセスを行う処理を並列化して高スループット化することができる。
【０１１４】
＜第２の実施の形態＞
以下、本発明における第２の実施の形態におけるデータベース装置の構成について図７を用いて説明する。なお、第２の実施の形態におけるデータベース装置１００において、図１に示されたデータベース装置１と同一の構成要素には同一の符号を用る。
【０１１５】
このデータベース装置１００においても、ＣＰＵ(Central Processing Unit)、メモリ、インタフェース等からなるコンピュータ（ハードウェア）にコンピュータプログラム（ソフトウェア）をインストールすることによって実現され、当該データベース装置１００の機能は、コンピュータの各種ハードウェア資源とコンピュータプログラムとが協働することによって実現される。また、コンピュータプログラムは、コンピュータ読取可能な記録媒体や記憶装置に格納された状態で提供されても良く、或いは電気通信回線を介して提供されても良い。
【０１１６】
このデータベース装置１００は、登録用のキーＫrのキー値（宛先アドレス値）を複数格納するＮ個の索引テーブル２[n] (n=0…N-1)、当該索引テーブル２[n] (n=0…N-1)に格納された複数のキー値（宛先アドレス値）にそれぞれ対応した複数のレコード値（転送先情報）を格納するレコードテーブル３、キー値に対応したレコード値の検索を制御する検索用の索引テーブル制御部１１０、キー値およびレコード値の登録を制御する登録用の索引テーブル制御部１１１、キー値に対応したレコード値をレコードテーブル３から取得する制御を行う検索用のレコードテーブル制御部１２０およびキー値に対応したレコード値をレコードテーブル３に格納する制御を行う登録用のレコードテーブル制御部１２１により構成されている。
【０１１７】
すなわち、第１の実施の形態におけるデータベース装置１との相違点は、当該データベース装置１では、１つの索引テーブル制御部４および１つのレコードテーブル制御部５を用いているが、第２の実施の形態におけるデータベース装置１００においては、検索用の索引テーブル制御部１１０、登録用の索引テーブル制御部１１１、検索用のレコードテーブル制御部１２０、登録用のレコードテーブル制御部１２１に分けられている点である。
【０１１８】
Ｎ個の索引テーブル２[n] (n=0…N-1)は、第１の実施の形態における索引テーブル２[n] (n=0…N-1)の構成と同じであるが、検索用の索引テーブル制御部１１０および登録用の索引テーブル制御部１１１から同時にアクセス可能なメモリが用いられている。ここで、検索用の索引テーブル制御部１１０および登録用の索引テーブル制御部１１１については、第１の実施の形態における索引テーブル制御部４のエントリ番号生成部４ａと同一の機能を有するエントリ番号生成部１１０ａおよび１１１ａが設けられている。
【０１１９】
同様に、レコードテーブル３は、第１の実施の形態と同様の構成であるが、Ｎ個の索引テーブル２[n] (n=0…N-1)と同様に、検索用のレコードテーブル制御部１２０および登録用のレコードテーブル制御部１２１から同時にアクセス可能なメモリが用いられている。
【０１２０】
索引テーブル登録部としての登録用の索引テーブル制御部１１１は、第１の実施の形態における索引テーブル制御部４の登録処理手順（図４）と同様の動作により登録用のキーＫrのキー値を索引テーブル２[n] (n=0…N-1)に登録する。索引テーブル検索部としての検索用の索引テーブル制御部１１０は、第１の実施の形態における索引テーブル制御部４の検索処理手順（図５）と同様の動作により検索用のキーＫsに対応したレコードＲsのレコード値をレコードテーブル３から取得する。
【０１２１】
レコードテーブル登録部としての登録用のレコードテーブル制御部１２１は、第１の実施の形態におけるレコードテーブル制御部５と同様に、登録用のキーＫrのキー値を索引テーブル２[n] (n=0…N-1)に登録するのに合わせて、当該キー値に対応したレコードＲrのレコード値をレコードテーブル３に登録する。レコードテーブル検索部としての検索用のレコードテーブル制御部１２０は、第１の実施の形態におけるレコードテーブル制御部５と同様に、検索用のキーＫsのキー値に対応したレコードＲsのレコード値をレコードテーブル３から検索して取得する。
【０１２２】
データベース装置１（図１）では、登録用および検索用を兼ねた索引テーブル制御部４およびレコードテーブル制御部５により、登録用のキーＫrに対する登録動作と検索用のキーＫsに基づく検索動作とを同時に行なわず、登録動作と検索動作とを順番に行うため、頻繁な登録処理によって検索処理のスループットが低下する場合がある。
【０１２３】
これに対してデータベース装置１００（図６）では、検索用の索引テーブル制御部１１０および登録用の索引テーブル制御部１１１により索引テーブル２[n] (n=0…N-1)に対して同時にキー値の登録処理および検索処理を実行できるとともに、検索用のレコードテーブル制御部１２０および登録用のレコードテーブル制御部１２１によりレコードテーブル３に対して同時にレコード値の登録処理および検索処理を実行できるので、キーＫrの登録処理によって検索処理のスループットを低下させることがないという効果を得ることができる。
【０１２４】
＜第３の実施の形態＞
以下、本発明における第３の実施の形態におけるデータベース装置の構成について図８を用いて説明する。なお、第３の実施の形態におけるデータベース装置２００において、図１に示されたデータベース装置１と同一の構成要素には同一の符号を用る。
【０１２５】
このデータベース装置２００においても、ＣＰＵ(Central Processing Unit)、メモリ、インタフェース等からなるコンピュータ（ハードウェア）にコンピュータプログラム（ソフトウェア）をインストールすることによって実現され、当該データベース装置２００の機能は、コンピュータの各種ハードウェア資源とコンピュータプログラムとが協働することによって実現される。また、コンピュータプログラムは、コンピュータ読取可能な記録媒体や記憶装置に格納された状態で提供されても良く、或いは電気通信回線を介して提供されても良い。
【０１２６】
＜データベース装置の全体構成＞
図８に示すように、第３の実施の形態におけるデータベース装置２００は、複数のキーに対応したキー値（宛先アドレス値）を格納するＮ個の索引テーブル２[n](n=0…N-1)、索引テーブル２[n] (n=0…N-1)に格納された複数のキー値（宛先アドレス値）にそれぞれ対応した複数のレコード値（転送先情報）を格納するＮ個のレコードテーブル３[n] (n=0…N-1)、索引テーブル２[n] (n=0…N-1)およびレコードテーブル３[n] (n=0…N-1)に対するキー値（宛先アドレス値）およびレコード値の検索動作を制御するＮ個の索引テーブル検索部２１０[n] (n=0…N-1)、キー値の索引テーブル２[n] (n=0…N-1)に対する登録動作を制御する索引テーブル登録部２１１によって構成されている。
【０１２７】
なお、データベース装置２００においては、Ｎ個の索引テーブル２[n] (n=0…N-1)およびＮ個のレコードテーブル３[n] (n=0…N-1)がそれぞれ対応付けられた組によって構成されている。また、索引テーブル２[n] (n=0…N-1)およびレコードテーブル３[n] (n=0…N-1)のそれぞれの組に対しては、索引テーブル登録部２１１および索引テーブル検索部２１０[n] (n=0…N-1)から同時にアクセス可能となっている。
【０１２８】
ところで第３の実施の形態におけるデータベース装置２００においても、第１の実施の形態におけるデータベース装置１と同様に、代表的な実装における索引テーブル数Ｎは「２」であり、第１の実施の形態のように、最少の回路規模でメモリ使用効率を従来のデータベース装置よりも大幅に改善することが可能である。
【０１２９】
また、データベース装置２００においては、索引テーブル数Ｎを「３」以上に増大させること、すなわち索引テーブル数Ｎに対応したＮ個のハッシュ関数ｆ[n](n=0〜3)を用いることが可能である。
【０１３０】
これによりデータベース装置２００は、１つのハッシュ関数f[n](n=1)を用いる場合に比べて、複数のハッシュ関数f[n] (n=0〜3) を用いることにより、複数の登録用のキーＫrから生成されるエントリ番号１１[n] (n=0〜3)が衝突する確率を低減させることができる。かくしてデータベース装置２００は、従来のデータベース装置のようにエントリ番号１１[i]の衝突が起きたときに、そのエントリ番号１１[i]のバケット１０[i]にバケットサイズＬ以上の複数のキー値が格納されることによるオーバーフローを未然に防止することが可能となる。
【０１３１】
＜索引テーブルの構成＞
索引テーブル２[n] (n=0…N-1)の構成は、第１の実施の形態と同一であり、その構成は図２に示された通りである。索引テーブル２[n] (n=0…N-1)はメモリであり、各索引テーブル２[n]はＭ個のエントリ１１[i](i=0…M-1)を有している。このエントリ１１[i](i=0…M-1)は、複数のキー値（宛先アドレス値）を格納可能なＬ個のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)が設けられたバケット１０[i](i=0…M-1)として構成されている。
【０１３２】
したがって、索引テーブル２[n](n=0…N-1)毎に設けられたキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)の個数は、各索引テーブル２[n] (n=0…N-1)のテーブルサイズＭ（索引テーブル２[n]のエントリ数（バケット数））×各バケットのバケットサイズＬ（キー格納位置１２[i][j]の個数）により表される。
【０１３３】
なお、索引テーブル２[n] (n=0…N-1)のテーブルサイズＭやバケットサイズＬは、索引テーブル２[n] (n=0…N-1)毎に異なる値とすることが可能であるが、代表的な実装における索引テーブルサイズＭやバケットサイズＬは、全索引テーブル２[n] (n=0…N-1)において同値とすることができる。
【０１３４】
これによりデータベース装置２００では、登録用のキーＫrの索引テーブル２[n] (n=0…N-1)に対する登録動作において、各索引テーブル２[n] (n=0…N-1)のバケット[n]のうち最小のバケット長[nr]に基づいて当該キーＫrのキー値を格納する索引テーブル２[n] (n=0…N-1)を選択する処理（ステップＳＰ５）を行う。これによりデータベース装置２００では、第１の実施の形態と同様に、索引テーブル２[n] (n=0…N-1)およびレコードテーブル３[n] (n=0…N-1)のメモリ使用効率を大幅に改善することが可能となる。
【０１３５】
＜レコードテーブルの構成＞
図９には、レコードテーブル３[n] (n=0…N-1)の構成例を示す。ここで、レコードテーブル３[0]、……、３[n]、……、３[N-1]は全て同じ構成であるため、ここでは便宜上、レコードテーブル３[n]について説明する。
【０１３６】
レコードテーブル３[n]はメモリであり、索引テーブル２[n]に対応し、当該索引テーブル２[n] のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に格納したキー値（宛先アドレス値）の各々に対応したレコード値（転送先情報）を格納可能なレコードエントリ２０[k](k=0…K-1)が設けられている。
【０１３７】
したがって、索引テーブル２[n](n=0…N-1)毎に設けられたキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)の個数は、上述したように、各索引テーブル２[n] (n=0…N-1)のテーブルサイズＭ×各バケットのバケットサイズＬにより表されるので、レコードテーブル３[n]の各レコードエントリ２０[k] (k=0…K-1)に１個のレコード値（転送先情報）を格納する１個のメモリとして構成した場合のレコードテーブル３[n]のレコードテーブルサイズＫは、Ｋ＝Ｍ×Ｌとなる。
【０１３８】
索引テーブル２[n]のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)と、レコードテーブル３[n]のレコードエントリ２０[k] (k=0…K-1)のレコードエントリ番号[k]との対応付けは、索引テーブル２[n] のキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に基づいてレコードエントリ２０[k] (k=0…K-1)のレコードエントリ番号[k]を一意に算出できる計算方法であればよい。
【０１３９】
例えば、１つの計算方法として、索引テーブル２[n]のエントリ１１[i]を示すエントリ番号[i] (i=0…M-1)、キー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)を示すバケット内キー格納位置番号[j](j=0…L-1)を用いて、レコードエントリ２０[k] (k=0…K-1)のレコードエントリ番号[k]を次の（式４）により算出することが可能である。
k＝i×L＋j…………………………………………………………（式４）
【０１４０】
＜索引テーブル登録部の構成＞
索引テーブル登録部およびレコードテーブル登録部としての索引テーブル登録部２１１は、外部から入力された登録用のキーＫrに基づいて各索引テーブル２[n] (n=0…N-1)のエントリ１１[i] (i=0…M-1)をそれぞれ特定するエントリ番号[i] (i=0…M-1)を生成するためのＮ個のハッシュ関数ｆ[n] (n=0…N-1)を備えている。
【０１４１】
また、索引テーブル登録部２１１は、登録用のキーＫr（宛先アドレス）から当該Ｎ個のハッシュ関数ｆ[n] (n=0…N-1)にそれぞれ対応したハッシュ値からなるＮ個のエントリ番号[n] (n=0…N-1)を生成するエントリ番号生成部２１１ａを有している。
【０１４２】
索引テーブル登録部２１１は、データベース装置１の転送データベース（各索引テーブル２[n] (n=0…N-1)およびレコードテーブル３[n] (n=0…N-1)）にキーＫrのキー値および当該キーＫrに対応したレコードＲrのレコード値を登録する場合、登録用のキーＫrおよび当該キーＫrと対応するレコードＲrを外部から入力する。
【０１４３】
そして索引テーブル登録部２１１は、第１の実施の形態における索引テーブル制御部４と同様に、索引テーブル２[n] (n=0…N-1)のうち最少のバケット長[nr]を持つバケット[nr]のキー値が未格納のキー格納位置１２[nr][jr]に当該キーＫrのキー値を格納するのと併せて、当該索引テーブル２[n] (n=0…N-1)と対応したレコードテーブル３[n] (n=0…N-1)のうち、当該キー格納位置１２[nr][jr]に対応したレコードエントリ２０[k] (k=0…K-1)に当該レコードＲrのレコード値を格納する。
【０１４４】
ところで、索引テーブル登録部２１１による登録用のキーＫrの登録動作において、各索引テーブル２[n] (n=0…N-1)の各エントリ番号[n] (n=0…N-1)により指定した各バケット１０[n] (n=0…N-1)について、バケット長（既に格納されているキー値の個数）もしくは空きバケット長（追加で格納可能なキー値の個数）を取得する必要がある。
【０１４５】
このため索引テーブル登録部２１１は、索引テーブル２[n] (n=0…N-1)の各々に対応して、当該索引テーブル２[n] (n=0…N-1)の各キー格納位置[i][j] (i=0…M-1) (j=0…L-1) 毎にキー値を格納しているか否かを表すキー格納マップテーブルＭＰ[n] (n=0…N-1)を備える。
【０１４６】
図１０には、キー格納マップテーブルＭＰ[n] (n=0…N-1)の構成例を示す。キー格納マップテーブルＭＰ[n]の実態はメモリであり、当該メモリをＭ個のエントリ２２０[i] (i=0…M-1)を有するテーブルとし、さらに、各エントリ２２０[i] (i=0…M-1)をＬ個のキー格納フラグ２２２[i][j] (i=0…M-1) (j=0…L-1)により構成する。ここで、キー格納フラグ２２２[i][j] (i=0…M-1) (j=0…L-1)は、各エントリ２２０[i] (i=0…M-1)のエントリ番号[i] (i=0…M-1)と、キー格納位置番号[j](j=0…L-1)によって特定される。
【０１４７】
キー格納フラグ２２２[i][j] (i=0…M-1) (j=0…L-1)は、当該キー格納フラグ２２２[i][j] (i=0…M-1) (j=0…L-1)と対応した索引テーブル２[n] (n=0…N-1)のキー格納位置[i][j] (i=0…M-1) (j=0…L-1)に登録用のキーＫrのキー値が格納されているか否かを表す１ビットの情報である。
【０１４８】
索引テーブル登録部２１１は、キー格納マップテーブルＭＰ[n] (n=0…N-1)のキー格納フラグ２２２[i][j] (i=0…M-1) (j=0…L-1)にセットされた値を取得することにより、索引テーブル２[n] (n=0…N-1)のキー格納位置[i][j] (i=0…M-1) (j=0…L-1)にキー値が格納されているか否かを知ることができる。
【０１４９】
また、索引テーブル登録部２１１は、索引テーブル２[n] (n=0…N-1)のバケット１０[i] (i=0…M-1)のバケット長もしくは空きバケット長を取得する場合は、キー格納マップテーブルＭＰ[n] (n=0…N-1)に含まれる全てのキー格納フラグ２２２[i][j] (i=0…M-1) (j=0…L-1)のうち、バケット１０[i] (i=0…M-1)にキー値を格納していることを示す（あるいはキー値を格納していないことを示す）フラグの個数を計数することによって認識することができる。
【０１５０】
索引テーブル登録部２１１は、初期状態（索引テーブル２[n] (n=0…N-1)に対して登録されたキー値が存在しない状態）において、キー格納マップテーブルＭＰ[n] (n=0…N-1)の全フラグをクリアしておき、キーＫrのキー値の登録に合わせて、当該登録したキー値のキー格納位置[i][j] (i=0…M-1) (j=0…L-1)に対応するキー格納フラグ２２２[i][j] (i=0…M-1) (j=0…L-1)のフラグをセットする。
【０１５１】
したがって索引テーブル登録部２１１は、キーＫrのキー値を登録するとき、バケット長の取得のために、各索引テーブル２[n] (n=0…N-1)の１個のバケット１０[i] (i=0…M-1)にアクセスし、当該バケット１０[i] (i=0…M-1)に格納されているキー値の個数を計数する必要がないので、各索引テーブル２[n] (n=0…N-1)の実態であるメモリに対するアクセスが発生しないのである。
【０１５２】
この場合、索引テーブル登録部２１１では、キー格納マップテーブルＭＰ[n] (n=0…N-1)の実態であるメモリに対するアクセスは発生するが、索引テーブル２[n] (n=0…N-1)の各エントリ１１[i] (i=0…M-1)は、キー値を格納できるビット数が必要であるのに対して、キー格納マップテーブルＭＰ[n] (n=0…N-1)の各エントリ２２０[i] (i=0…M-1)はキー値１個につき１ビットのビット数だけしか必要としない。したがって、索引テーブル２[n] (n=0…N-1)のメモリにアクセスする場合と比較して、キー格納マップテーブルＭＰ[n] (n=0…N-1)に対してアクセスする方が一段と少ない電力消費で済むという効果がある。
【０１５３】
＜索引テーブル検索部の構成＞
索引テーブル検索部およびレコードテーブル検索部としての各索引テーブル検索部２１０[n] (n=0…N-1)は、外部から入力する検索用のキーＫsを索引テーブル２[n] (n=0…N-1)のエントリ番号[n] (n=0…N-1)に変換するため、索引テーブル２[n] (n=0…N-1)にそれぞれ対応した１個のハッシュ関数f[n] (n=0…N-1)を備えている。すなわち、索引テーブル検索部２１０[0]はハッシュ関数f[0]を備え、索引テーブル検索部２１０[n]はハッシュ関数f[n]を備え、索引テーブル検索部２１０[N-1]はハッシュ関数f[N-1]を備えている。
【０１５４】
レコードテーブル３[n] (n=0…N-1)から検索用のキーＫsのキー値に対応したレコードＲsのレコード値を取得する場合、最初に索引テーブル検索部２１０[0]は、検索用のキーＫsを外部から入力し、ハッシュ関数f[0]により生成したエントリ番号[0]により指定される索引テーブル２[0]のバケット１０[0]に格納された複数のキー値の中から検索用のキーＫsと一致するキー値を探索する。
【０１５５】
索引テーブル検索部２１０[0]は、索引テーブル２[0] のバケット１０[0]に検索用のキーＫsと一致するキー値を見つけた場合、見つけたキー値の索引テーブル２[0]におけるキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に対応したレコードテーブル[0]のレコードエントリ２０[k] (k=0…K-1)から検索対象となるレコードＲsのレコード値を取得する。
【０１５６】
そして索引テーブル検索部２１０[0]は、レコードＲsのレコード値を含み、かつ、キーＫsに対応したレコードＲsのレコード値を既に取得済であることを表す検索有効な検索結果Ｈ[0]を次の索引テーブル検索部２１０[1]へ出力する。
【０１５７】
一方、索引テーブル検索部２１０[0]は、索引テーブル２[0]ののバケット１０[0]に検索用のキーＫsと一致するキー値を見つけられなかった場合、次の  索引テーブル検索部２１０[1]により索引テーブル２[1]の中から検索用のキーＫsと一致するキー値を見つけるため、当該キーＫsと、当該キーＫsに対応したレコードＲsのレコード値が未取得であることを表す検索無効な検索結果Ｈ[1]を次の索引テーブル検索部２１０[2]へ出力する。以下、同様の処理を索引テーブル検索部２１０[n] (n=0…N-1)は繰り返す。
【０１５８】
索引テーブル検索部２１０[n] (n=0…N-1)は、検索有効を意味する検索結果Ｈ[n-1]を前段の索引テーブル検索部２１０[n-1]から受け取った場合、索引テーブル２[n] の中から検索用のキーＫsと一致するキー値を探索することなく、その検索有効を意味する検索結果Ｈ[n-1]をそのまま検索有効を意味する検索結果Ｈ[n]として後段の索引テーブル検索部２１０[n+1]へ出力する。
【０１５９】
また、索引テーブル検索部２１０[n] (n=0…N-1)は、検索無効を意味する検索結果Ｈ[n-1]と、検索用のキーＫsを前段の索引テーブル検索部２１０[n-1]から受け取った場合、索引テーブル２[n] の中から検索用のキーＫsと一致するキー値を探索する。
【０１６０】
索引テーブル検索部２１０[n] (n=0…N-1)は、索引テーブル２[n] の中から検索用のキーＫsと一致するキー値を見つけた場合、索引テーブル２[n]のうち、当該キー値が格納されているキー格納位置１２[i][j] (i=0…M-1) (j=0…L-1)に対応したレコードテーブル３[n]のレコードエントリ２０[k] (k=0…K-1)から当該キー値に対応するレコードＲsのレコード値を取得する。
【０１６１】
索引テーブル検索部２１０[n]は、レコードＲsのレコード値を含み、かつ、キーＫsに対応したレコードＲsのレコード値を既に取得済であることを表す検索有効な検索結果Ｈ[n]を後段に出力する。
【０１６２】
さらに、索引テーブル検索部２１０[n] (n=0…N-1)は、索引テーブル２[n] の中から検索用のキーＫsと一致するキー値を見つけられなかった場合、キーＫsと、当該キーＫsに対応するレコードＲsのレコード値が未取得であることを表す検索無効な検索結果Ｈ[n]を後段に出力する。
【０１６３】
なお、索引テーブル検索部２１０[n] (n=0…N-1)では、検索用のキーＫsに対する各索引テーブル検索部２１０[n] (n=0…N-1)による検索が完了するまで、次のキーＫsの検索を保留する必要はない。索引テーブル検索部２１０[n] (n=0…N-1)の各々が外部または前段から入力した検索用のキーＫsに対する検索動作を終えて検索結果Ｈ[n]を出力し終えた後は、索引テーブル検索部２１０[n] (n=0…N-1)は次の検索用のキーＫsの入力を受け付けて検索動作を開始する、いわゆるパイプライン処理が可能である。
【０１６４】
また、索引テーブル検索部２１０[n] (n=0…N-1)では、各索引テーブル検索部２１０[n] (n=0…N-1)が検索用のキーＫsを入力してから検索結果Ｈ[n]を出力するまでに要する時間を、検索の有無（入力した検索結果Ｈ[n-1]が有効か無効か）や、検索用のキーＫsと一致するキー値が索引テーブル[n] (n=0…N-1)の中から見つけられたか否かに係らず一定とする。これにより、索引テーブル検索部２１０[n-1]と索引テーブル検索部２１０[n]との間で、検索用のキーＫsや検索結果Ｈ[n] (n=0…N-1)の滞留がない（すなわちボトルネックのない）パイプライン処理を可能とすることができる。
【０１６５】
＜索引テーブル登録部による登録処理＞
次に、索引テーブル登録部２１１が行う登録用のキーＫrの登録処理について、図１１のフローチャートを参照しながら説明する。
【０１６６】
データベース装置２００では、登録用のキーＫrおよび当該キーＫrに対応する登録対象のレコードＲrを登録する場合、索引テーブル制御部２１１は、外部から登録用のキーＫrおよびレコードＲrを入力する（ステップＳＰ２１）。
【０１６７】
索引テーブル登録部２１１は、各索引テーブル２[n] (n=0…N-1)にそれぞれ対応したＮ個のハッシュ関数ｆ[n] (n=0…N-1)を用いて、外部から入力した登録用のキーＫrからＮ個のエントリ番号[n] (n=0…N-1)を同時に生成する（ステップＳＰ２２[0]、……、ステップＳＰ２２[n]、……、ステップＳＰ２２[N-1]）。
【０１６８】
索引テーブル登録部２１１は、各エントリ番号[n] (n=0…N-1)に対応した各索引テーブル２[n] (n=0…N-1)の各バケット１０[n] (n=0…N-1)のバケット長[n] (n=0…N-1)を取得するに当たり、各キー格納マップテーブルＭＰ[n] (n=0…N-1)のエントリ２２０[n] (n=0…N-1)に含まれるキー格納フラグ２２２[n][j] (j=0…L-1)にセットされたフラグの個数を計数することによって、各索引テーブル２[n] (n=0…N-1)のバケット１０[n] (n=0…N-1)のバケット長[n] (n=0…N-1)を取得する（ステップＳＰ２３[0]、……、ステップＳＰ２３[n]、……、ステップＳＰ２３[N-1]）。ここで、キー格納フラグ２２２[n][j] (j=0…L-1)における[n]はエントリ番号[n]である。
【０１６９】
なお、索引テーブル登録部２１１は、バケット長[n] (n=0…N-1)を取得する代わりに、追加で格納可能なキー値の個数である空きバケット長[n](n=0…N-1)を取得するようにしてもよい。
【０１７０】
索引テーブル登録部２１１は、索引テーブル２[n] (n=0…N-1)の何れかのバケット１０[n] (n=0…N-1)に対してキーＫrのキー値を格納するため、各バケット長[n] (n=0…N-1)の中から最小値をとるバケット長[nr]を探索し、その最小値のバケット長[nr]に対応した索引テーブル２[nr]を選択する（ステップＳＰ２４）。
【０１７１】
索引テーブル登録部２１１は、索引テーブル２[nr]のキー格納位置１２[nr][j] (j=0…L-1)のうち、キー値が未格納のキー格納位置１２[nr][jr]を探索する（ステップＳＰ２５）。ここで、キー格納位置１２[nr][jr] における[nr]は、キー格納位置１２を特定する最小値のバケット長[nr]に対応したエントリ番号[nr]であり、[jr]はキー値が未格納のキー格納位置を特定するバケット内キー格納位置番号[jr]である。
【０１７２】
具体的には、索引テーブル登録部２１１は、索引テーブル２[nr]に対応したキー格納マップテーブルＭＰ[nr]のキー格納フラグ２２２[nr][j] (j=0…L-1)を全て読み出し、その中からキー値が未格納であることを示すキー格納フラグ２２２[nr][jr]に対応する索引テーブル２[nr]のキー格納位置１２[nr][jr]を探索する（ステップＳＰ２５）。
【０１７３】
索引テーブル登録部２１１は、キー値が未格納である索引テーブル２[nr]のキー格納位置１２[nr][jr]を見つけられたか否かを判定し（ステップＳＰ２６）、見つけられた場合には索引テーブル２[nr]のエントリ１１[nr]（バケット１０[nr]）におけるキー格納位置１２[nr][jr]に対して登録用のキーＫrのキー値を格納する（ステップＳＰ２７）。
【０１７４】
索引テーブル登録部２１１は、索引テーブル２[nr]のエントリ１１[nr] （バケット１０[nr]）におけるキー格納位置１２[nr][jr]に対して登録用のキーＫrのキー値を格納したので、エントリ番号[nr]、キー格納位置１２[nr][jr]のバケット内キー格納位置番号[jr]を上述した（式４）に代入する。
【０１７５】
これにより索引テーブル登録部２１１は、レコードテーブル３[nr]のレコードエントリ２０[kr]のレコードエントリ番号[kr]を次の（式５）により算出し、当該エントリ番号[kr]のレコードエントリ２０[kr]に対してレコードＲrのレコード値を格納し、登録有効を示す登録結果Ｔｋを出力することにより登録処理を終了する（ステップＳＰ２８）。
kr＝エントリ番号[nr]×L＋jr…………………………………………………………（式５）
【０１７６】
一方、索引テーブル登録部２１１は、キー値が未格納である索引テーブル２[nr]のキー格納位置１２[nr][jr]を見つけられなかった場合（ステップＳＰ２６：Ｎｏ）、すなわち登録用のキーＫrのキー値を登録できない場合には、登録不可時の処理として、登録無効を示す登録結果Ｔｆを出力することにより登録処理を終了する（ステップＳＰ２９）。
【０１７７】
なお索引テーブル登録部２１１は、登録無効を示す登録結果Ｔｆを出力することと併せて、登録用のキーＫrのキー値を登録できない回数をカウンタにより計数し、計数する度に更新し、その計数値を保持することができる。
【０１７８】
また索引テーブル登録部２１１は、登録無効を示す登録結果Ｔｆを出力することと併せて、索引テーブル２[nr]のエントリ１１[nr]（バケット１０[nr]）に対して既に格納済のキー値のうち、１個のキー値の登録を抹消し、その抹消したキー格納位置１２に対して登録用のキーＫrのキー値を登録するとともに、そのキー格納位置１２に対応したレコードテーブル３[n]のレコードエントリ２０[k]にレコードＲrのレコード値を格納することもできる。
【０１７９】
なお索引テーブル登録部２１１は、キー格納マップテーブルＭＰ[n] (n=0…N-1)に基づいて各バケット長[n] (n=0…N-1)の中から最小値をとるバケット長[nr]を探索し、その最小値のバケット長[nr]に対応した索引テーブル２[nr]を選択するようにしたが（ステップＳＰ２４）、これに限るものではなく、登録対象とすべき索引テーブル２[nr]を選択する索引テーブル選択方法としては、それ以外にも以下の３通りが存在する。
【０１８０】
一つ目の索引テーブル選択方法は、キー格納マップテーブルＭＰ[n] (n=0…N-1)に基づいて空きバケット長[n] (n=0…N-1)が０よりも大きいバケット１０[n] (n=0…N-1)の中から索引テーブル番号[n] (n=0…N-1)が最小の索引テーブル番号[nr]を持つ索引テーブル２[nr]を選択する。
【０１８１】
二つ目の索引テーブル選択方法は、キー格納マップテーブルＭＰ[n] (n=0…N-1)に基づいて空きバケット長[n] (n=0…N-1)の中から最大値をとる空きバケット長[nr] となった索引テーブル番号[nr]を持つ索引テーブル２[nr]を選択する。
【０１８２】
三つ目の索引テーブル選択方法は、各索引テーブル２[n] (n=0…N-1)が異なるテーブルサイズＭ（エントリ１１[i]の個数）である場合に、キー格納マップテーブルＭＰ[n] (n=0…N-1)に基づいて取得した空きバケット長[n] (n=0…N-1)を索引テーブル２[n] (n=0…N-1)毎に設定された重み係数で重み付けした重み付け空きバケット長[n] (n=0…N-1)のうち、最大値をとる重み付け空きバケット長[nr]となった索引テーブル番号[nr]を持つ索引テーブル２[nr]を選択する。
【０１８３】
なお、一つ目乃至三つ目の索引テーブル選択方法においては、各索引テーブル２[n] (n=0…N-1)のバケットサイズＬ（キー格納位置１２[nr][jr] (i=0…M-1) (j=0…L-1)の個数）が異なる場合にも適用することができる。
【０１８４】
＜索引テーブル検索部による検索処理＞
次に、各索引テーブル検索部２１０[n] (n=0…N-1)がそれぞれ行う検索用のキーＫsに基づく検索対象のレコードＲsの検索処理について、図１２のフローチャートを参照しながら説明する。
【０１８５】
データベース装置２００では、検索用のキーＫsおよび当該キーＫsに対応して登録されている検索対象のレコードＲrを検索する場合、索引テーブル検索部２１０[n] (n=0…N-1)は、外部または前段の索引テーブル検索部２１０[n-1]から検索用のキーＫsと、前段の索引テーブル検索部２１０[n-1]からの検索結果Ｈ[n-1]を入力する（ステップＳＰ３１）。
【０１８６】
ここで、索引テーブル検索部２１０[n] (n=0…N-1)においては、索引テーブル検索部２１０[n]が[n]=０の場合には、前段の索引テーブル検索部２１０[n-1]が存在しないため、検索用のキーＫsだけを入力する。しかしながら、索引テーブル検索部２１０[n]が[n]＞０の場合には、前段の索引テーブル検索部２１０[n-1]が存在するので、検索用のキーｋsおよび前段からの検索結果Ｈ[n-1]の双方を入力する。
【０１８７】
索引テーブル検索部２１０[n] (n=0…N-1)は、自身が[n]＝０の索引テーブル検索部２１０[0]であるか、または、前段の索引テーブル検索部２１０[n-1]から検索無効の検索結果Ｈ[n-1]を受け取ったか否かを判定する（ステップＳＰ３２）。
【０１８８】
索引テーブル検索部２１０[n] (n=0…N-1)は、自身が[n]＝０の索引テーブル検索部２１０[0]でない場合（ステップＳＰ３２：ＮＯ）、または、前段の索引テーブル検索部２１０[n-1]から検索無効の検索結果Ｈ[n-1]を受け取っていない場合、すなわち検索有効の検索結果Ｈ[n-1]を受け取った場合（ステップＳＰ３２：ＮＯ）、その検索有効の検索結果Ｈ[n-1]をそのまま検索結果Ｈ[n]として後段に出力し（ステップＳＰ３３）、処理を終了する。
【０１８９】
索引テーブル検索部２１０[n] (n=0…N-1)は、自身が[n]＝０の索引テーブル検索部２１０[0]である場合（ステップＳＰ３２：ＹＥＳ）、または、前段の索引テーブル検索部２１０[n-1]から無効の検索結果Ｈ[n-1]を受け取った場合（ステップＳＰ３２：ＹＥＳ）、自身が持つ１つのハッシュ関数f[n] (n=0…N-1)を用いて検索用のキーＫsから索引テーブル２[n]の検索対象を指し示すエントリ番号[is]を生成する（ステップＳＰ３４）。
【０１９０】
索引テーブル検索部２１０[n] (n=0…N-1)は、当該索引テーブル検索部２１０[n] (n=0…N-1)と対応した索引テーブル２[n] (n=0…N-1)におけるエントリ番号[is]のバケット[is]に格納されている最大Ｌ個のキー値を取得する（ステップＳＰ３５）。
【０１９１】
索引テーブル検索部２１０[n] (n=0…N-1)は、索引テーブル２[n] (n=0…N-1)におけるエントリ番号[is]のバケット[is]から取得した最大Ｌ個のキー値のうち、検索用のキーＫsと一致するキー値の格納されていたキー格納位置１２[is][js]を探索する（ステップＳＰ３６）。
【０１９２】
索引テーブル検索部２１０[n] (n=0…N-1)は、最大Ｌ個のキー値のうち、検索用のキーＫsと一致するキー値を見つけられたか否かを判定し（ステップＳＰ３７）、見つけられなかった場合には（ステップＳＰ３７：ＮＯ）、当該検索用のキーＫsと検索無効を示す検索結果Ｈ[n]を後段に出力し（ステップＳＰ３８）、処理を終了する。
【０１９３】
索引テーブル検索部２１０[n] (n=0…N-1)は、最大Ｌ個のキー値のうち、検索用のキーＫsと一致するキー値が見つけられた場合（ステップＳＰ３７：ＹＥＳ）、キー格納位置１２[is][js]に対応したレコードテーブル３[n]のレコードエントリ番号[ks]を、エントリ番号[is]、キー格納位置１２[is][js]のバケット内キー格納位置番号[js]に基づいて（式６）により算出し、当該レコードエントリ番号[ks]のレコードエントリ２０[ks]から検索対象のレコードＲsのレコード値を取得する（ステップＳＰ３９）。
ks＝エントリ番号[is]×L＋js…………………………………………………………（式６）
【０１９４】
索引テーブル検索部２１０[n] (n=0…N-1)は、検索対象のレコードＲsのレコード値を取得したので、当該レコードＲsのレコード値を含み、かつ、検索用のキーＫsに対応する検索対象のレコードＲsを取得済であることを表す検索有効の検索結果Ｈ[n]を後段に出力し（ステップＳＰ４０）、処理を終了する。
【０１９５】
＜第３の実施の形態における効果＞
索引テーブル検索部２１０[n]は、当該索引テーブル検索部２１０[n]と対応する索引テーブル２[n] (n=0…N-1)のなかから検索用のキーＫsに一致するキー値を見つけることができた場合、検索有効の検索結果Ｈ[n]を後段の索引テーブル検索部２１０[n+1]に出力することができる。
【０１９６】
また、索引テーブル検索部２１０[n] (n=0…N-1)は、前段の索引テーブル検索部２１０[n-1] から検索有効の検索結果Ｈ[n-1]を受け取った場合、索引テーブル２[n] (n=0…N-1)のなかから検索用のキーＫsに一致するキー値の探索を行うことなく、当該検索結果Ｈ[n-1]をそのまま検索結果Ｈ[n]として後段の索引テーブル検索部２１０[n+1]に出力することができる。
【０１９７】
これにより索引テーブル検索部２１０[n] (n=0…N-1)は、索引テーブル２[n] (n=0…N-1)のなかから検索用のキーＫsに一致するキー値を見つけることができた場合、後段の索引テーブル検索部２１０[n+1]、索引テーブル検索部２１０[n+2]、……、索引テーブル検索部２１０[N-1]については、検索用のキーＫsと一致するキー値を探索するための索引テーブル２[n+1]、索引テーブル２[n+2]、……索引テーブル２[N-1]に対するアクセスは行われない。
【０１９８】
したがって、検索用のキーＫsを入力したとき、当該索引テーブル検索部２１０[n] (n=0…N-1)にそれぞれ対応した索引テーブル２[n] (n=0…N-1)に対して一斉にアクセスし、検索用のキーＫsに一致するキー値を探索する場合と比較し、索引テーブル検索部２１０[n] (n=0…N-1)は、索引テーブル２[n] (n=0…N-1)に対するアクセス頻度を低減することができ、その結果、索引テーブル２[n] (n=0…N-1)へのアクセスにより生じる電力消費を低減することができる。
【０１９９】
なお、索引テーブル登録部２１１による登録用のキーＫrの登録動作については、キー格納マップテーブルＭＰ[n] (n=0…N-1)を用いることにより、登録用のキーＫrのキー値を格納すべき索引テーブル２[n]のみにアクセスし、その他の索引テーブル２[n]についてはアクセスしない。これにより、各索引テーブル検索部２１０[n] (n=0…N-1)は検索処理のパイプライン動作を停止する必要がなく、また前段から検索無効の検索結果Ｈ[n-1]が与えられたとき検索用のキーＫsと一致するキー値の探索を行うための索引テーブル２[n]に対するアクセスを停止する必要がない。
【０２００】
さらに、索引テーブル登録部２１１では、上述した登録処理（図１１）におけるステップＳＰ２３[0]、…、ステップＳＰ２３[n]、…、ステップＳＰ[N-1]のように、全てのキー格納マップテーブルＭＰ[n] (n=0…N-1)に同時にアクセスしている。これに対して、パイプライン処理によって各キー格納マップテーブルＭＰ[n] (n=0…N-1)に順番にアクセスするという構成を用いた場合、全てのキー格納マップテーブルＭＰ[n] (n=0…N-1)に対するアクセスが終わらないとバケット長が最少の索引テーブル２[n] (n=0…N-1)を選出することができない。このため、選出する必要のない無効なキー格納マップテーブルＭＰ[n] (n=0…N-1)に対するアクセスを停止することができず、その分消費電力を削減することができなくなるという問題が生じてしまう。
【０２０１】
さらに、上述したようなパイプライン処理によって各キー格納マップテーブルＭＰ[n] (n=0…N-1)に順番にアクセスするという構成では、登録用のキーＫrの登録開始から登録完了までの時間が長くなるため、登録用のキーＫrが登録完了するまでは当該キーＫrの検索処理を実行できないという問題も生じてしまう。
【０２０２】
しかしながら、第３の実施の形態におけるデータベース装置２００では、上述したような問題が生じることもなく、第１の実施の形態のように、メモリ使用効率を高めることができると同時に、かつ消費電力効果を向上させることができる。
【０２０３】
＜他の実施の形態＞
なお上述した第２の実施の形態においては、１つのレコードテーブル３（図７）を用いるようにした場合について述べたが、本発明はこれに限るものではなく、第１の実施の形態に対応した他の実施の形態のように、Ｎ個のメモリからなるレコードテーブル３[n] (n=0…N-1)を用いるようにしても良い。
【符号の説明】
【０２０４】
１、１００、２００…データベース装置、２[n]…索引テーブル、３、３[n]…レコードテーブル、４…索引テーブル制御部（索引テーブル登録部、索引テーブル検索部）、５…レコードテーブル制御部（レコードテーブル登録部、レコードテーブル検索部）、１０[i]…バケット、１１[i]…エントリ、１２[i][j]…キー格納位置、２０[k]…レコードエントリ、１１０…検索用の索引テーブル制御部（索引テーブル検索部）、１１１…登録用の索引テーブル制御部（索引テーブル登録部）、１２０…検索用のレコードテーブル制御部（レコードテーブル検索部）、１２１…登録用のレコードテーブル制御部（レコードテーブル登録部）、２１０[n]…索引テーブル検索部（索引テーブル検索部、レコードテーブル検索部）、２１１…索引テーブル登録部（索引テーブル登録部、レコードテーブル登録部）、２２２[i][j]…キー格納フラグ、ＭＰ…キー格納マップテーブル。
【図１】
2016015011.tif 000003
【図２】
2016015011.tif 000004
【図３】
2016015011.tif 000005
【図４】
2016015011.tif 000006
【図５】
2016015011.tif 000007
【図６】
2016015011.tif 000008
【図７】
2016015011.tif 000009
【図８】
2016015011.tif 000010
【図９】
2016015011.tif 000011
【図１０】
2016015011.tif 000012
【図１１】
2016015011.tif 000013
【図１２】
2016015011.tif 000014