(57)【特許請求の範囲】
【請求項１】
複数のデータと各データに対応する検索用の識別情報とを格納するデータ部と、
前記各識別情報がハッシュ関数に従って変換された前記識別情報のビット長よりも短いハッシュ値を格納した第１索引テーブルであって、ハッシュ値としてとり得る値が相互に重ならないように区分けされた所定の数値範囲の夫々に対応する複数のブロックを有し、各ブロックには、そのブロックに対応する数値範囲に夫々属する前記変換されたハッシュ値と、各ハッシュ値に対応する識別情報と、各識別情報の前記データ部における格納位置とが格納された第１索引テーブルと、
前記第１索引テーブルの各ブロックに対応する数値範囲の最大値又は最小値、及び、各最大値又は最小値の前記第１索引テーブルにおける格納位置、を格納する第２索引テーブルと、
データ検索時に入力された識別情報をハッシュ値に変換し、このハッシュ値と第２索引テーブルに格納された各最大値又は最小値との大小を比較して当該ハッシュ値が属する数値範囲に対応する最大値又は最小値を特定し、該最大値又は最小値の第１索引テーブルにおける格納位置に基づき、当該ハッシュ値と同一のハッシュ値が格納された前記第１索引テーブルのブロックを特定し、そのブロックに格納された各ハッシュ値と前記変換されたハッシュ値とを対比して同一のハッシュ値を検索し、検索したハッシュ値に対応する識別情報と検索用に入力した識別情報とを対比して同一の識別情報を検索対象として特定し、この識別情報の前記データ部における格納位置より前記データ部から対応データを検索する検索手段と、
を備えたデータ管理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデータ管理装置に関する。さらに詳細には、データ部に格納したデータを、各データに対応する識別情報とデータの格納位置とを格納した索引を用いて管理するデータ管理装置に関する。
【０００２】
【従来の技術】
一般に、記憶手段に格納した複数のデータを管理するため、このデータから抽出した検索用の識別情報とデータの格納位置とを格納する索引を作成し、データへのアクセス時間を短縮して検索効率を向上するようにしている。
【０００３】
例えば、図５に示すように、従来のデータ管理装置は、記憶手段２０に形成され複数のデータと各データに対応する識別情報とを格納したデータ部５０と、この各データの識別情報とデータ部における各データの格納位置を示すポインタとを二組格納する二つのブロック４１、４２からなる第１の索引テーブル４０と、第１の索引テーブル４０の見出しとなる識別情報を格納した第２の索引テーブル３０と、この第１の索引テーブル４０と第２の索引テーブル３０とを用いてデータ部５０のデータを検索する検索手段１３とを備えている。
【０００４】
そして、データ部５０にはデータとして氏名が格納され、識別情報として従業員番号が格納されている。また、第２の索引テーブル３０は、各ブロック４１、４２に格納した識別情報のうち大きい値が格納されている。
【０００５】
このようなデータ管理装置において、例えば、氏名上田、従業員番号５７８７を検索する場合を説明する。まず、検索手段１３に従業員番号５７８７を入力する。すると、検索手段１３が、第２の索引テーブル３０において、従業員番号５７８７と第２の索引テーブル３０に格納されている従業員番号とを対比する。そして、第１索引テーブル４０のうち、従業員番号５７８７が格納されるブロック４１を特定する。
【０００６】
次に、ブロック４１において、入力された従業員番号５７８７と格納されている従業員番号とを対比して検索対象の従業員番号５７８７を特定する。最後にこの従業員番号５７８７に対応するポインタの指示に従い、データ部５０から氏名上田を検索する。
【０００７】
【発明が解決しようとする課題】
しかし、従来のデータ管理装置は、前記例のように、第１の索引テーブル４０と第２の索引テーブル３０とに識別情報を格納しデータ検索の際のキーとしている。このため、識別情報のビット長が長い場合や複数の識別情報に対する索引（複合インデックス）の場合は、各索引テーブル３０、４０に格納される情報量が大きくなり、データのアクセスに時間を要するという問題点がある。
【０００８】
本発明は、前記問題点に鑑みなされたものであり、索引テーブルに格納される情報量を減少し、データへの検索時間を短縮し得るデータ管理装置を提供することを技術的課題とする。
【０００９】
【課題を解決するための手段】
本発明は、データ管理装置であって、前記技術的課題を解決するために以下の手段を採用する。
【００１０】
すなわち、複数のデータと各データに対応する検索用の識別情報とを格納するデータ部と、
前記各識別情報がハッシュ関数に従って変換された前記識別情報のビット長よりも短いハッシュ値を格納した第１索引テーブルであって、ハッシュ値としてとり得る値が相互に重ならないように区分けされた所定の数値範囲の夫々に対応する複数のブロックを有し、各ブロックには、そのブロックに対応する数値範囲に夫々属する前記変換されたハッシュ値と、各ハッシュ値に対応する識別情報と、各識別情報の前記データ部における格納位置とが格納された第１索引テーブルと、
前記第１索引テーブルの各ブロックに対応する数値範囲の最大値又は最小値、及び、各最大値又は最小値の前記第１索引テーブルにおける格納位置、を格納する第２索引テーブルと、
データ検索時に入力された識別情報をハッシュ値に変換し、このハッシュ値と第２索引テーブルに格納された各最大値又は最小値との大小を比較して当該ハッシュ値が属する数値範囲に対応する最大値又は最小値を特定し、該最大値又は最小値の第１索引テーブルにおける格納位置に基づき、当該ハッシュ値と同一のハッシュ値が格納された前記第１索引テーブルのブロックを特定し、そのブロックに格納された各ハッシュ値と前記変換されたハッシュ値とを対比して同一のハッシュ値を検索し、検索したハッシュ値に対応する識別情報と検索用に入力した識別情報とを対比して同一の識別情報を検索対象として特定し、この識別情報の前記データ部における格納位置より前記データ部から対応データを検索する検索手段と、を備えている。
【００１１】
以下、本発明の構成要素を説明する。
（データ部）データ部は、複数のデータと各データに対応する検索用の識別情報を格納するものである。識別情報は、データの一部を指定したものでも良く、また、別個に指定したものでも良い。識別情報には、例えば、データが氏名である場合は、年齢、従業員番号、生年月日等が用いられる。このデータ部は、例えばテーブル状にし、各データと識別情報とを組として格納するのが好ましい。
【００１２】
（ハッシュ変換手段）
ハッシュ変換手段は、識別情報をハッシュ関数に従って識別情報のビット長よりも短いハッシュ値に変換し、索引テーブルに格納する情報量を小さくするものである。このハッシュ変換手段は、ハッシュ関数を格納してあり、識別情報が入力されると、識別情報をハッシュ値に変換するようにしてある。ハッシュ関数は一定の法則に基づき識別情報を短いハッシュ値に変換できるものであれば良い。
【００１３】
例えば、ハッシュ関数を以下のように定義しても良い。
データ＝ａｂｃｄ
ハッシュ関数ｈ＝（ａｂ＋ｃｄ）ｍｏｄ１００
このようなハッシュ関数により、例えば識別情報５４４３を変換すると、ハッシュ値は９７となり、識別情報よりも短いものとなる。この変換されたハッシュ値は、第１の索引テーブルと第２の索引テーブルとに格納され、この格納したハッシュ値を検索することによりデータ部に格納したデータの検索を行う。
【００１４】
（第１索引テーブル）
第１索引テーブルは、データ部に格納した各データの索引となるものである。この第１索引テーブルは複数のブロックからなる。各ブロックには、ハッシュ変換手段により変換されたハッシュ値を複数所定範囲でまとめたハッシュ値群が格納される。
【００１５】
この所定範囲は、自由に定め得るものであるが、変換されたハッシュ値の分布状況を考慮し、各ハッシュ値群がほぼ同数の変換されたハッシュ値を有するようにまとめる。なお、ブロックの数は、このハッシュ値群の数に対応して設ける。このとき、ブロックに格納するハッシュ値の数が多くなり、ブロック内の検索に時間がかからないようにする。また、各ブロックに格納されるハッシュ値は、大きい順または小さい順に並べて格納し、各ブロックの先頭には各ハッシュ値群の最大値または最小値を格納するのが好ましい。
【００１６】
例えば、ハッシュ値が９９，４４，９１及び９７の４つ存在する場合は、ハッッシュ値を大きい順に並べ、９９と９７とで一つのハッシュ値群を形成し、所定範囲をハッシュ値９９から９２までと定める。また、同様にして９１と４４とでもう一つのハッシュ値群を形成し、所定範囲を９１から００と定める。そして、第１索引テーブルを２つのブロックから構成し、ブロックの一方にハッシュ値９９を先頭として格納し、ブロックの他方にハッシュ値９１を先頭として格納する。なお、この後に、追加されたデータの識別情報がハッシュ値７０に変換された場合は、ブロックの他方にハッシュ値７０を格納する。もっとも、データの増加に伴い、変換されたハッシュ値の数が増加した場合は、所定範囲を変更してブロック数を増加しても良い。
【００１７】
また、各ブロックにはハッシュ値に対応する識別情報が格納される。これは、例えば二つの識別情報をハッシュ値に変換すると、識別情報の値が異なるにも拘わらずハッシュ値が同一値となる場合がある（ハッシュ値の衝突）。従って、この識別情報を格納しないと、ハッシュ値によりデータを検索した場合に、いずれの識別情報に対応するハッシュ値であるのか判断できず、データ検索が不正確なものとなるおそれがある。このため、ハッシュ値を変換する元となった識別情報をハッシュ値とともに格納することにより、ハッシュ値の衝突によるデータ検索ミスを回避しようとするものである。従って、一つのハッシュ値に対応する識別情報が複数ある場合は、その全てを格納する。
【００１８】
さらに、各ブロックには、データ部における識別情報の格納位置を格納する。これらのハッシュ値と識別情報と格納位置とは一組として各ブロックに格納するのが良い。
【００１９】
なお、各ブロックにはさらに一つのハッシュ値に属する識別情報の格納数を格納するようにしても良い。
（第２索引テーブル）
第２索引テーブルは、第１索引テーブルの索引の役目を果たすものである。この第２索引テーブルは、第１索引テーブルの各ブロックの先頭に格納されるハッシュ値を格納する。この第２索引テーブルに格納されるハッシュ値は、第１索引テーブルの各ブロックの見出しとされる。また、この見出しとなるハッシュ値の第１索引テーブルにおける格納位置を格納する。なお、格納されるハッシュ値は、大きい順か小さい順にならべて格納するのが好ましい。
【００２０】
この第２索引テーブルにより、データ検索の際に、まず第２索引テーブルを検索し、第１テーブルのどのブロックに検索データの識別情報を変換したハッシュ値が格納されているかを特定できるようにする。
【００２１】
例えば、ハッシュ値が上限を９９とし下限を００とする場合において、０から５０までのハッシュ値を所定範囲とするブロックと、５１から９９までのハッシュ値を所定範囲とするブロックとから第１索引テーブルが形成されている場合には、第２索引テーブルにハッシュ値９９とハッシュ値５０とを格納する。そして、検索データのハッシュ値が例えば７０である場合は、５０と７０を対比し、さらに９９と７０とを対比し、５０＜７０≦９９と特定し、ハッシュ値５１からハッシュ値９９までを所定範囲とするブロックを検索するようにする。
【００２２】
なお、この第２索引テーブルに格納するハッシュ値の数は、第１の索引テーブルのブロック数に対応するものであるが、この格納数が増加した場合は、第２の索引に格納されたハッシュ値を所定範囲のハッシュ値群に分けるとともに、第２索引テーブルを各ハッシュ値群を格納する複数のブロックからなるようにし、さらに上位に第３の索引テーブルを作成し、この第２の索引テーブルに格納したハッシュ値の格納位置と、第２の索引テーブルに格納したハッシュ値の見出しとなるハッシュ値とを格納するようにしても良い。要するに本発明は、格納されるデータの数に応じて索引テーブルを２階層以上に形成しても良いものであり、幾階層に形成しても良いものである。
【００２３】
（検索手段）
検索手段は、ハッシュ変換手段により変換したハッシュ値に基づき、第２索引テーブル、第１索引テーブルの順に検索し、データ部に格納したデータを検索するものである。
【００２４】
検索手段は、まずデータ検索時に入力された識別情報をハッシュ値に変換する。次に、第２索引テーブルにおいて、変換されたハッシュ値と第２索引テーブルとに格納されたハッシュ値との大小を比較する。そして、同一のハッシュ値が格納されたブロックを特定する。
【００２５】
このブロックの特定にあたり、例えば、検索手段に、予めハッシュ値群の所定の範囲と先頭の値を登録しておく。そして、検索手段が変換したハッシュ値と格納された各ハッシュ値との大小を順に比較して、変換したハッシュ値が含まれるハッシュ値群を特定するようにする。そして、特定されたハッシュ値群の先頭に格納されるハッシュ値に対応して格納された第１索引テーブルの格納位置に従って第１索引テーブルのブロックを検索するようにする。
【００２６】
次に、特定したハッシュ値群を格納するブロックにおいて変換したハッシュ値と同一のハッシュ値を検索する。これは、例えば、変換したハッシュ値と特定ブロックに格納されたハッシュ値とを順次対比し、一致するハッシュ値を検索することにより行う。
【００２７】
次に検索した同一のハッシュに対応して格納されている識別情報と検索用に入力した識別情報とを対比して同一の識別情報を検索し、この識別情報を検索対象として特定する。このとき、第１索引テーブルにハッシュ値に対応する識別情報を格納しておくと、検索手段が識別情報同士を対比する回数を指定することができる点で好ましい。
【００２８】
最後に、この識別情報より前記データ部から対応データを検索する。これは、識別情報に対応して格納されているデータ部における対象データの格納位置に従ってデータ部を検索することにより行う。
【００２９】
（本発明の付随的構成要素）
本発明のデータ管理装置は、以上説明した必須の構成要素からなるものであるが、以下に説明する付随的構成要素を付加した場合であっても成立する。
【００３０】
（登録手段）
本発明のデータ管理装置は、新規データを追加したとき、第１索引テーブルにおいて、前記新規データに対応する新規識別情報のハッシュ値がすでに存在するときは、そのハッシュ値下に属するものとして前記新規識別情報とこの識別情報に対応するデータのデータ部における格納位置とを前記第１索引テーブルに登録する登録手段を備えていても良い。
【００３１】
（削除手段）
登録手段に加え、さらに、データを削除する際、削除データに対応する識別情報のハッシュ値を検索し、第１索引テーブルにおいて、前記ハッシュ値に属する識別情報が１つ格納されているとき、当該識別情報とハッシュ値とを削除し、そのハッシュ値に属する識別情報が複数格納されているとき、削除データ対応の識別情報を削除する削除手段を備えても良い。
【００３２】
このように登録手段と削除手段とを備えると、データの追加と削除とに対応して第１索引テーブルと第２索引テーブルとの格納内容が変更されることとなり、検索手段は、適切な内容の第１索引テーブルと第２索引テーブルとを検索してデータ検索を行うことが可能となる。
【００３３】
（本発明の作用）
本発明のデータ管理装置によると、データと識別情報とがデータ部に格納されると、ハッシュ変換手段は、識別情報をハッシュ関数に従って識別情報のビット長より短いハッシュ値に変換する。このハッシュ値は、第１索引テーブルに格納される。また、ハッシュ値群の先頭となるハッシュ値は、第２索引テーブルに格納される。また、第１索引テーブルには、格納したハッシュ値に対応する識別情報が格納され、さらにデータ部における各データの格納位置が格納される。
【００３４】
また、第２索引テーブルには、格納したハッシュ値の第１の索引テーブルにおける格納位置が格納され、第２索引テーブルに格納した各ハッシュ値の第１索引テーブルにおける格納位置が格納される。
【００３５】
次に、データ検索時のデータ管理装置の作用を説明する。
検索手段にデータの識別情報が入力されると、検索手段は、まず、入力された識別情報をハッシュ値に変換する。次に、第２索引テーブルにおいて、変換したハッシュ値と第２索引テーブルに格納されたハッシュ値とを比較して同一のハッシュ値が格納された第１索引テーブルのブロックを特定する。
【００３６】
例えば、第２索引テーブルにハッシュ値９９と９１が格納されている場合において、検索手段がある識別情報をハッシュ値９３に変換したとする。この場合、検索手段は第２索引テーブルにおいて、ハッシュ値９３とハッシュ値９９とを比較し９３≦９９と認識する。また、検索手段は、ハッシュ値９３とハッシュ値９１とを比較して９１＜９３≦９９と認識する。これにより、変換したハッシュ値９３が含まれるハッシュ値群を特定する。すなわち、第２索引テーブルに格納されたハッシュ値９９は、ハッシュ値９９からハッシュ値９２までを所定範囲とする第１検索テーブルのブロックの見出しと認識する。
【００３７】
このように、ブロックを特定すると、検索手段は、第２索引テーブルに格納されているハッシュ値と同一のハッシュ値が第１索引テーブルに格納されている位置の指示に従い、特定した第１索引テーブルにおいて、変換したハッシュ値と同一のハッシュ値を対比することにより検索する。この同一のハッシュ値を検索すると、このハッシュ値に対応して格納された識別情報と検索用に入力されたハッシュ値とを対比して一致する識別情報を検索対象として特定する。これは、識別情報が複数の場合は、一致する識別情報を検索するまで繰り返して行われる。
【００３８】
最後に、検索対象として特定した識別情報に対応するデータ部のデータ格納位置の指示に従いデータ部から対応データを検索する。
なお、第１検索テーブルに一つのハッシュ値に属する識別情報の格納数が格納されている場合は、第１索引テーブルの特定ブロックにおいて同一のハッシュ値を検索した際、検索したハッシュ値下に属する識別情報の格納数が一つのときはその識別情報により記憶手段から対応データを検索する。
【００３９】
一方、検索したハッシュ値下に属する識別情報の格納数が複数のときは検索用に入力された識別情報とハッシュ値下に属する複数の識別情報とを対比して、同一の識別情報を検索対象として特定する。そして、当該識別情報によりデータ部から対応データを検索する。
【００４０】
また、本発明が登録手段を備える場合は以下のようになる。
データ部に新規データを追加した際、新規データに対応する識別情報はハッシュ変換手段によりハッシュ値に変換される。登録手段は、このハッシュ値により、第２索引テーブルにおいて変換したハッシュ値を格納したブロックを特定し、第１索引テーブルにおいて既に同一のハッシュ値が格納されているかを調べる。そして、新規識別情報のハッシュ値が既に第１索引テーブルに存在するときは、新規識別情報をそのハッシュ値下に属するものとして第１索引テーブルに登録し、さらにこの新規識別情報に対応するデータのデータ部における格納位置を登録する。一方、新規識別情報のハッシュ値が第１索引テーブルに存在しない場合は、ハッシュ値、識別情報、データ部における格納位置を登録する。
【００４１】
さらに、本発明が削除手段を備える場合は以下のようになる。
データ部からデータを削除する際、削除手段は削除データに対応する識別情報のハッシュ値をデータ検索の際と同様にして、第１索引テーブルにおいて検索する。そして、そのハッシュ値に属する識別情報が１つ格納されているとき、当該識別情報とハッシュ値と削除データのデータ部における格納位置を削除する。
【００４２】
一方、そのハッシュ値に属する識別情報が複数格納されているとき、削除手段は削除データ対応の識別情報を削除し、さらに削除した識別情報に対応する削除データのデータ部における格納位置を削除する。
【００４３】
【発明の実施の形態】
以下、本発明のデータ管理装置の好適な実施の形態を図を用いてさらに詳細に説明する。図１には、本実施の形態にかかるデータ管理装置１０の概要が示されている。このデータ管理装置１０は、ハッシュ変換部１２と、検索部１３と、登録部１４と、削除部１５と、第２索引テーブル３０と、第１索引テーブル４０とを備える。
【００４４】
なお、このデータ管理装置１０は、記憶部２０に形成したデータ部５０にデータである氏名と識別情報である従業員番号とを格納して管理するものである。
〈実施の形態のハード的構成〉
実施の形態にかかるデータ管理装置１０は、ハード的には、システムバスを介して接続されたＣＰＵと主記憶装置と補助記憶装置とから構成されている。データ管理装置１０の構成要素のうち、ハッシュ変換部１２と検索部１３と登録部１４と削除部１５とは、補助記憶装置に格納されたプログラムであり、必要に応じて主記憶装置に読み出され、ＣＰＵによりロードされて実現する機能である。
【００４５】
〈記憶部〉
記憶部２０には補助記憶装置が用いられている。この補助記憶装置は、フロッピーディスク、ハードディスク、ＭＯ（Magnet Optical）等を用いることができる。この記憶部２０に氏名と従業員番号を対応させて格納するためのデータ部５０が形成されている。
【００４６】
〈データ部〉
データ部５０は、二つのセル縦列により形成されている。そして、左側のセル縦列に従業員番号がそれぞれ格納され、右側のセル縦列に従業員番号に対応する氏名が格納される。ここでは、６人の氏名がデータとして格納されており、また、各氏名に対応する従業員番号がそれぞれ格納されている。
【００４７】
〈ハッシュ変換部〉
ハッシュ変換部１２は、入力された従業員番号をハッシュ関数に従って従業員番号のビット長よりも短いハッシュ値に変換するものである。このハッシュ変換部１２には一定の法則に基づくハッシュ関数が格納されている。ここで用いられているハッシュ関数は、氏名に対応する従業員番号を１バイト単位に区切り、区切ったそれぞれの値を合計するものがである。数式で表せば、
従業員番号＝ａｂｃｄ
ｈ＝（ａｂ＋ｃｄ） ｍｏｄ １００
である。従ってハッシュ値の上限は９９であり、下限は００である。
【００４８】
ハッシュ変換部１２は、このハッシュ値を必要に応じて検索部１３、登録部１４、削除部１５のいずれかに送るようにしてある。
〈第１索引テーブル〉
第１索引テーブル４０は、第１ブロック４１と第２ブロック４２とから形成されている。各ブロック４１、４２は、４つのセル縦列から形成されている。このセル縦列のうち、左端のセル縦列には、ハッシュ変換部１２により変換されたハッシュ値が上から大きい順に並べて格納される。また、左から２番目のセル縦列は、一つのハッシュ値に属する従業員番号の数が格納される。さらに、左から３番目のセル縦列はハッシュ値に対応する従業員番号が格納される。そして、右端のセル縦列は、データ部５０における従業員番号と氏名との格納位置を示すポインタが格納される。
【００４９】
なお、従業員番号を格納するセルとポインタを格納するセルとは、ハッシュ値の衝突が生じる場合には横に分割され、それぞれの従業員番号が格納される。また、ポインタを格納するセルには、データ部５０における各従業員番号及び氏名の格納位置がそれぞれ格納される。
【００５０】
この第１索引テーブル４０の第１ブロック４１は、先頭をハッシュ値９９とし所定範囲をハッシュ値９９からハッシュ値９２までとし、この範囲のハッシュ値を格納するものである。また、第２ブロック４２は、先頭をハッシュ値９１とし所定範囲をハッシュ値９１からハッシュ値００までとし、この範囲のハッシュ値を格納するものである。
【００５１】
〈第２索引テーブル〉
第２索引テーブル３０は、二つのセル縦列から形成され、左側のセル縦列には、ハッシュ変換部１２により変換されたハッシュ値のうち、第１索引テーブル４０の各ブロックの先頭に格納されるハッシュ値が、上から大きい順に格納される。右側のセル縦列にはここに格納された各ハッシュ値の第１索引テーブル４０における格納位置を示すポインタが格納される。
【００５２】
ここでは、第２索引テーブルには、ハッシュ値９９とハッシュ値９１とが格納されている。このハッシュ値９９は、第１索引テーブルにおけるハッシュ値９９から９２までのハッシュ値群を格納する第１ブロック４１の見出しとなっている。また、ハッシュ値９１は、ハッシュ値９１から００までのハッシュ値群を格納する第２ブロック４２の見出しとなっている。
【００５３】
〈検索部〉
検索部１３は、第２索引テーブル３０、第１索引テーブル４０の順に検索してデータ部５０からデータを検索するものである。
【００５４】
この検索部１３は、ハッシュ関数を有し、従業員番号が入力されると、従業員番号をハッシュ値に変換するようにされている。検索部１３は、変換したハッシュ値により第２索引テーブル３０を検索し、変換したハッシュ値と同一のハッシュ値が格納されているブロックを、第１ブロック４１と第２ブロック４２とのいずれか一方から特定する。これは、変換したハッシュ値と、第２索引テーブル３０に格納されているハッシュ値との大小を順に比較することにより、ハッシュ値が属するハッシュ値群を特定することにより行う。
【００５５】
検索部１３は、各ハッシュ値群の先頭の値であるハッシュ値９９とハッシュ値９１とを有しており、その特定したハッシュ値群の先頭に格納されているハッシュ値９９またはハッシュ値９１に対応して格納されたポインタに従い、第１索引テーブル４０の第１ブロック４１と第２ブロック４２との一方において変換したハッシュ値を検索する。
【００５６】
次に、検索したハッシュ値に対応する従業員番号と検索用に入力した従業員番号とを対比し、同一の従業員番号を検索対象として特定する。最後に、この従業員番号に対応して格納されたポインタの指示に従いデータ部５０から氏名を検索するようにされている。
【００５７】
〈登録部〉
登録部１４は、氏名と従業員番号とが入力されると、データ部５０にこれらを登録するようにされている。また、ハッシュ変換部１２からハッシュ値が入力されるようになっており、ハッシュ値が入力されると、第２索引テーブル３０において、ハッシュ値を格納する第１索引テーブルのブロックを第１ブロック４１と第２ブロック４２との一方から特定する。次に特定したブロックにおいて、ハッシュ値とこのハッシュ値に対応する従業員番号とこの従業員番号のデータ部５０における格納位置を示すポインタとを格納し、さらに、一つのハッシュ値下に属する従業員番号の格納数を１つ加算するようにされている。
【００５８】
もっとも、第１索引テーブル４０の特定したブロックにおいて、入力されたハッシュ値と同一のハッシュ値が既に格納されている場合は、そのハッシュ値に属するものとして従業員番号を第１索引テーブル４０に登録するとともに、当該ハッシュ値に属する従業員番号数の値を１つ加算するようにされている。
【００５９】
〈削除部〉
削除部１４は、氏名と従業員番号とが入力されると、データ部５０から氏名と従業員番号とを削除するようにされている。また、ハッシュ変換部１２からハッシュ値が入力される。すると、まず、第２索引テーブル３０において、入力されたハッシュ値と格納されたハッシュ値との大小を比較して、同一のハッシュ値が格納されたブロックを第１ブロック４１と第２ブロック４２との一方から特定する。
【００６０】
次に、特定した第１索引テーブル４０のブロックにおいて、削除氏名に対応する従業員番号のハッシュ値を検索する。そして、そのハッシュ値に属する従業員番号が１のとき、当該従業員番号とハッシュ値とポインタとを削除するとともに従業員番号の格納数を１つ減算するようにされている。
【００６１】
このとき、ハッシュ値に属する従業員番号の格納数が複数のときは、入力された従業員番号と格納されている従業員番号とを対比して、削除氏名対応の従業員番号を特定する。そして、この従業員番号とポインタとを削除するとともに、当該ハッシュ値下に属する従業員番号の数の値を１つ減算するようにされている。
【００６２】
〈実施の形態の作用〉
以上説明したデータ管理装置１０の作用を図１と図２とを用いて説明する。例えば、氏名香川、従業員番号５４４３を新規に登録する場合と追加する場合とにおけるデータ管理１０の動作について説明する。
【００６３】
まず、登録部１４に氏名香川、従業員番号５４４３が入力されると、登録部１４はこれらをデータ部５０に登録する。このとき、ハッシュ変換部１２に従業員番号５４４３が入力される。
【００６４】
次にハッシュ変換部１２は従業員番号５４４３をハッシュ値９７に変換する。すなわちｈ＝（５４＋４３）ｍｏｄ１００＝９７である。このハッシュ値９７は登録部１４に入力される。
【００６５】
次に、登録部１４は、この変換されたハッシュ値９７と第２索引テーブル３０に格納されているハッシュ値９９との大小を比較し９７≦９９と認識する。同様にハッシュ値９７とハッシュ値９１との大小を比較し、９１＜９７と認識する。これにより、登録部１４は、ハッシュ値９７を格納するハッシュ値群の所定範囲は、９１＜９７≦９９と認識する。このとき、登録部１４に格納されているハッシュ値群の先頭の値９９より、登録部１４は、ハッシュ値９９が先頭に格納されている第１ブロック４１をハッシュ値９７が格納されるブロックと特定する。
【００６６】
次に、第２索引テーブル３０に格納されたハッシュ値９９に対応するポインタの指示に従い、第１ブロック４１において変換したハッシュ値９７と格納してあるハッシュ値とを先頭のハッシュ値９９から順に対比することにより同一のハッシュ値９７を検索する。
【００６７】
このとき、第１ブロック４１には同一のハッシュ値９７は格納されていないものとする。登録部１４は、未だハッシュ値９７が格納されていないことを認識すると、第１ブロック４１にハッシュ値９７を登録する。また、このハッシュ値９７を変換する元になった従業員番号５４４３とデータ部５０における従業員番号５４４３の格納位置を示すポインタとを登録する。また、ハッシュ値９７下に属する従業員番号の格納数を１つ換算する。
【００６８】
なお、第１ブロック４１に既にハッシュ値９７が格納されている場合は、同一のハッシュ値９７を検索すると、登録部１４は、ハッシュ値９７に対応する従業員番号を格納するセルに既に格納されている従業員番号５４４３に加え、従業員番号４３５４を登録する。また、従業員番号４３５４のデータ部５０における格納位置を示すポインタを登録する。さらに、ハッシュ値９７下に属する従業員番号の格納数１に１つ加算し２とする。
【００６９】
このようにして、次々とデータを登録すると、図１に示すデータ部５０と第１索引テーブル４０とのようになる。このようなデータの格納状況において、データ部５０から、例えば、氏名佐々木、従業員番号４３５４を検索する場合のデータ管理装置１０の動作を図１と図３とを用いて以下に説明する。
【００７０】
まず、検索部１３に従業員番号４３５４が入力される。すると、検索部１３はハッシュ関数を呼び出し、ｈ＝（４３＋５４）ｍｏｄ１００＝９７の演算を行い、従業員番号４３５４をハッシュ値９７に変換する。次に、検索部１３はハッシュ値９７により、第２索引テーブル３０において、変換されたハッシュ値９７と格納されているハッシュ値９９とを比較し、９７≦９９と認識する。
【００７１】
同様にハッシュ値９７とハッシュ値９１との大小を比較し、９１＜９７と認識する。これにより、検索部１３は、ハッシュ値９７を格納するハッシュ値群の所定範囲は、９１＜９７≦９９と認識する。このとき、検索部１３に格納されているハッシュ値群の先頭の値９９より、検索部１３は、ハッシュ値９９が先頭に格納されている第１ブロック４１をハッシュ値９７が格納されるブロックと特定する。
【００７２】
次に、第２索引テーブル３０に格納されたハッシュ値９９に対応して格納されたポインタの指示に従い、第１ブロック４１において変換したハッシュ値９７と格納してあるハッシュ値とを先頭のハッシュ値９９から順に対比することにより同一のハッシュ値９７を検索する。
【００７３】
この同一のハッシュ値９７を検索すると、次に検索部１３は、このハッシュ値９７下に属する従業員番号の格納数２を検索し、格納されている従業員番号と、検索用に入力された従業員番号４３５４との比較を最大２回行えば良いことを認識する。そして、従業員番号を上から順に対比し、２回目の対比において、同一の従業員番号４３５４を検索し、この同一の従業員番号４３５４を検索対象として特定する。
【００７４】
最後に、この従業員番号４３５４に対応して格納されたデータ部５０における従業員番号４３５４の格納位置を示すポインタに従い、データ部５０から氏名佐々木を検索する。
【００７５】
このとき、ハッシュ値９７下に属する従業員番号の格納数が１である場合は、従業員番号の対比を一度だけ行い検索対象を特定し、従業員番号４３５４に対応するポインタに従ってデータ部５０から氏名佐々木を検索する。
【００７６】
なお、検索部１３は、第１索引テーブル４０においてハッシュ値９７を検索できないときは該当氏名なしのメッセージを出し、ＣＲＴ等の出力装置が表示するようにされている。
【００７７】
〈データの削除〉
次に、データ部５０に格納した氏名山田、従業員番号８１１０を削除する場合のデータ管理装置１０の動作を図１と図４とを用いて以下に説明する。
【００７８】
まず、削除部１５に氏名山田と従業員番号８１１０とが入力されると、ハッシュ変換部１２に従業員番号８１１０が入力される。すると、ハッシュ変換部１２がハッシュ関数を呼び出し、ｈ＝（８１＋１０）ｍｏｄ１００＝９１の演算を行い、従業員番号８１１０をハッシュ値９１に変換する。このハッシュ値９１は削除部１５に送られる。
【００７９】
次に、削除部１５は、この変換されたハッシュ値９１と第２索引テーブル３０に格納されているハッシュ値９９との大小を比較し９１≦９９と認識する。次ににハッシュ値９１とハッシュ値９１とを比較し、９１≦９１と認識する。この場合は、変換したハッシュ値９１がハッシュ値群の先頭の値９１と一致するため、削除部１５は、ハッシュ値９１が先頭に格納されている第２ブロック４２をハッシュ値９１が格納されるブロックと特定する。
【００８０】
次に、第２索引テーブル３０に格納されたハッシュ値９１に対応するポインタの指示に従い、第１ブロック４１において変換したハッシュ値９１と格納してあるハッシュ値とを先頭のハッシュ値９９から順に対比することにより同一のハッシュ値９１を検索する。
【００８１】
このとき、ハッシュ値９１下に属する従業員番号の格納数が１である場合は、入力された従業員番号８１１０と格納されている従業員番号８１１０とを１回対比し、削除データに対応する従業員番号８１１０を特定する。そして、第１索引テーブル４０からハッシュ値９１と従業員番号８１１０とポインタとを削除する。また、ハッシュ値９１下に属する従業員番号の格納数を１つ減算する。
【００８２】
そして、削除するポインタをもとに、データ部５０から氏名山田と従業員番号８１１０とを削除する。
一方、従業員番号の格納数が複数の場合、すなわち、図１のように、従業員番号８１１０の他に従業員番号１０８１が格納されている場合は、入力された従業員番号８１１０と格納されている従業員番号との対比を最大２回行えば良いことを認識する。そして、従業員番号の格納順に上から対比を行い、一回目の対比で従業員番号同士が一致するため、この従業員番号８１１０を削除氏名に対応する従業員番号８１１０と特定する。そして、第１索引テーブル４０の第２ブロック４２から従業員番号８１１０とこの８１１０に対応するポインタとを削除する。また、ハッシュ値９１下に属する従業員番号の格納数を一つ減算する。
【００８３】
そして、ポインタをもとに、データ部５０から氏名山田と従業員番号８１１０とを削除する。
〈データの更新〉
データ部５０に格納した氏名を更新する場合におけるデータ管理装置の動作は、データ部５０から氏名と従業員番号とを削除し、続けて氏名と従業員番号とを追加する場合の動作と同様にして行われる。したがって、詳細な説明は省略する。
【００８４】
〈実施の形態の効果〉
以上説明した実施の形態にかかるデータ管理装置の効果を以下に述べる。
データ管理装置１０によると、第２索引テーブル３０と第１索引テーブル４０とには、ハッシュ変換手段１２により変換されたハッシュ値が格納されている。このハッシュ値は、元の識別情報である従業員番号に比べると２分の１のビット長である。従って、第２索引テーブル３０と第１索引テーブル４０とに格納された情報量は全体として減少する。このため、検索部１３は、データ検索を短時間で行うことができる。
【００８５】
また、第２索引テーブル３０を有しているため、変換されたハッシュ値が格納されたブロック４１、４２を早く検索することができる。
また、登録部１４と削除部１５とを備えることにより、常に最新のデータ部５０の格納内容に対応する索引テーブル３０と第１索引テーブル４０とを再編成することができる。この再編成も短時間で処理することができる。
【００８６】
また、第１索引テーブル４０に従業員番号を格納するため、ハッシュ値の衝突が生じる場合であっても、検索手段は正確にデータを検索することができる。
【００８７】
【発明の効果】
本発明のデータ管理装置によると、ハッシュ変換手段によりデータの識別情報をハッシュ関数に従って識別情報のビット長よりも短いハッシュ値に変換するため、索引テーブルに格納する情報量の減少を図ることができる。このため、記憶手段に格納したデータの検索時間を短縮することができる。また、ハッシュ値の衝突の発生に拘わらず適切にデータを検索することができる。
【図面の簡単な説明】
【図１】図１は、本発明の実施の形態にかかるデータ管理装置の概要を示すブロック図である。
【図２】図２は、データ部にデータを登録する際におけるデータ管理装置の動作の手順を示すフローチャートである。
【図３】図４は、データ部に格納したデータを検索する際におけるデータ管理装置の動作の手順を示すフローチャートである。
【図４】図４は、データ部からデータを削除する際におけるデータ管理装置の動作の手順を示すフローチャートである。
【図５】図５は、従来のデータ管理装置の概要を示すブロック図である。
【符号の説明】
１２    ハッシュ変換部
１３    検索部
１４    登録部
１５    削除部
２０    記憶部
３０    第２索引テーブル
４０    第１索引テーブル
４１    第１ブロック
４２    第２ブロック
５０    データ部
【図１】
0003647940.tif 000002
【図２】
0003647940.tif 000003
【図３】
0003647940.tif 000004
【図４】
0003647940.tif 000005
【図５】
0003647940.tif 000006