[0001]【発明の属する技術分野】本発明は、データベース管理システムにおけるハッシュ表管理装置に関し、特にシノニム(同義語)の管理に関するものである。[0002]【従来の技術】従来、この種のハッシュ表管理は、キーの衝突が多数発生しても検索効率を低下させないために、例えば特開平1−099131号公報に示されるように、同一のハッシュ値に変換された異なるキーを二分木構造でチェーンさせてハッシュ表に登録し、または検索する方式を採っている。[0003]【発明が解決しようとする課題】しかし、上述した従来の技術では、二分木構造に新しいキーを登録するときに、常に木構造の末端の節の下に新しいキーを管理する節を作成するので、木構造にキーを登録する順序によって偏りができてしまうため、キーの登録順によって検索時の性能が低下するという問題点がある。データベース管理システムにおいては、数十万あるいは数百万のオーダのレコードを扱うことと、キーの指定によっては上記のような偏りが発生しやすいという特徴があるので、上述の問題は、より深刻なものとなる。serious.【0004】したがって、本発明の目的は、キーの登録順がハッシュ表検索の検索効率に影響を与えないようなハッシュ表管理装置を提供することにある。記憶内容を逆順に参照しながら二分木をバランス処理する二分木バランス手段とを有することを特徴とする。invention,図面を参照して説明する。105.【0008】ハッシュ表103は、各エントリに、キーを管理する二分木構造のルートのアドレスを持っている。20102を起点に左右に分かれる二分木構造のルートが図示されている。二分木を構成する各節の構造は、図3に示すように、キー値と左部分木のポインタと、右部分木のポインタと、左部分木の深さと、右部分木の深さを情報に持つ。section,この節の左部分木の節で管理されている。この節で管理するキー値より大きいキー値は、この節の右部分木以下の節で管理されている。102を用いて検索(詳細は後述する)を行なう。検索の結果、未登録キーならば、このキーを管理する新たな節を作成し、検索手段102から返却された最後に比較した節のアドレスを参照し、その節の左部分木または右部分木に新たに作成した節をチェーンする。その後、二分木バランス手段104を用いて、節を追加したことによる各節における左右の部分木の深さの情報を更新すると共に、アンバランスを修正する。105の指す節以下の部分木に対し左右の部分木の深さを更新し、その結果、左右の部分木の深さの差が2以上になる節に対しては、深さの差が1以下になるようにバランス処理を行なう。less.【0011】検索手段102は、与えられたキー値をハッシュし、ハッシュ値からハッシュ表103上のエントリを選択し、そのエントリに繋がっている二分木に対し、与えられたキー値による二分木検索を行なう。この二分木検索の結果、同一キーを管理する節が見つかれば、その旨のフラグとのそ節のアドレスを返却し、見つからなければ最後に比較した節のアドレスを返却する。105.【0012】次に、本実施例について、さらに詳細に説明する。detail.【0013】図2は、ハッシュ表エントリで管理するバランスされた二分木とその節の管理内容を示した説明図である。図2を参照すると、ハッシュ表の一つのエントリが二分木構造のルートの節202のアドレスを管理している。各節は、図3に示すように、左部分木のポインタ、左部分木の深さ、右部分木のポインタ、右部分木の深さ、およびキー値を情報として持つ。202以下の二分木は、どの節を調べても、左右の部分木の深さの差は1以下であり、また、各節で管理するキー値よりも小さいキー値はこの節の左部分木以下の節で管理され、大きいキー値は右部分木以下の節で管理されている。105と、二分木に節を登録した後のバランス処理による二分木の変化を示した説明図である。process03をチェーンした直後の状態である。302は、二分木ポインタ301が指す節から順番に、節304のアドレスおよび右部分木検索の情報、節305のアドレスおよび右部分木検索の情報、節306のアドレスおよび左部分木検索の情報を記録している。306の左部分木の深さは登録以前の状態である。registration.【0015】図5に示す二分木は、上記説明の二分木に対しバランス処理を施した結果の状態を表している。308およびその左部分木で表される通り変化しない。節305は節309の左部分木としてポイントされ、節310となる。節306は節309の右部分木としてポイントされ、節311となる。311.【0016】図6は二分木バランス手段104によるバランス処理の流れを示す図である。6,401では、初期設定として、一つ前にバランス処理した節のポインタを保持するためのPRIORに、登録する節303のアドレスを設定する。306)のアドレスとこの節において左部分木を検索したか右部分木を検索したかの情報を取り出す(402)。このとき、全て参照し終ったら(403)、処理を終了する。二分木検索記録により左部分木検索か右部分木検索かをチェックし(404)、図4の例のように左部分木検索ならば、405にて当該節306の左部分木のポインタにポインタPRIORの保持するアドレスを設定する。306,PROIRの指す節の左右の部分木の深さ(現時点では共に0)の大きい方の値+1を設定する。逆に、右部分木検索であったなら、406において左部分木と同様に、右部分木のポインタと深さを設定する。as06に節303がチェーンされたことになる。chain.【0018】上記処理の結果、407において現在の節306の左右の部分木の深さの差が2以上になったかどうかチェックする。図4の例では、深さの差は1である。深さの差が2以上ならば408でバランス処理ルーチンを呼び出しバランス処理する。バランス処理が不要なら現在の節306のアドレスをPRIORに設定し(409)、402の処理以降を繰り返す。402.【0019】図4の例では、節305について以上の処理が繰り返される。今回は、404にて右検索と判断され、406にて、PRIORに保持された節306の左部分木の深さ1に+1された2が現在の節305の右部分木の深さとなる。この結果、407にて、節305の左部分木の深さ0と、右部分木の深さの差が2以上となるのでバランス処理ルーチン408に入ることになる。more.【0020】図7は、408で呼び出すバランス処理ルーチンの流れ図である。バランス処理は深さの差が2以上になる場合に動作するものなので、現在の節、その下位の節、さらにその下位の節の3レベルの節間でポインタチェーンを張り替える処理である。図7を参照すると、先ず、現在の節の検索経路を調べる(501)。(501).【0021】図4の例のように、現在の節305の検索経路が右ならば、さらに一つ前の節306の検索経路を調べる(505)。306の左部分木の節303をTOPの節とする。TOPの節306の左部分木には現在の節305を繋ぎ、右部分木には現在の節305の右部分木の節306を繋ぐ。303の右部分木の節306の左部分木として繋ぐ。この結果、図4の二分木は図5のようにバランスする。TOP,TOPの左部分木を現在の節の右部分木に繋ぎ、現在の節をTOPの左部分木に繋ぐ。TOP.【0023】一方、501において、検索経路が左ならば、さらに一つ前の節の検索経路を調べる(502)。(502).一つ前の節の検索経路が右ならば、503で、一つ前の節の右部分木の節をTOPの節とする。TOPの右部分木には現在の節を繋ぎ、左部分木には現在の節の左部分木を繋ぐ。TOPの右部分木の節の左部分木として繋ぐ。TOP,TOPの右部分木を現在の節の左部分木に繋ぎ、現在の節をTOPの右部分木に繋ぐ。TOP.【0025】508で左右の部分木のポインタを繋ぎ替えた節について左右の部分木の深さについても更新する。最後に、TOPの節をバランス処理結果の節として呼び出し元に返却する(509)。2以上の場合にバランス処理ルーチン408に入るが、これを3以上または4以上というように、処理ルーチンに入る機会を少なくしてもよい。逆順に参照するのを二分木構造のトップに至るまで行っているが、途中迄にしてもよい。[0028]【発明の効果】本発明によれば、二分木構造をバランスすることにより、二分木の一部の部分木の深さが深くなり、その部分のツリーチェーンを辿る検索効率が悪くなることを防ぐことができる。DRAWINGS【図1】本発明のデータベース管理システムにおけるハッシュ表管理装置を示すブロック図である。invention.【図2】本発明のハッシュ表エントリで管理するバランスされた二分木例を示した説明図である。invention.【図3】本発明における節の構造を示す図である。二分木に節を登録した後のバランス処理前二分木を示した説明図である。tree.【図5】図4に示した二分木についてのバランス処理後の状態を示した説明図である。FIG.【図6】本発明を用いた二分木バランス処理の流れを示すフローチャートである。FIG.【図7】図6の二分木バランス処理のなかで呼び出すバランス処理ルーチンの流れを示すフローチャートである。記憶内容を逆順に参照しながら二分木をバランス処理する二分木バランス手段とを有することを特徴としたハッシュ表管理装置。記憶内容が左(右)なら、当該節の左(右)部分木の深さを、一つ前にバランス処理した節の左部分木の深さと右部分木の深さのうちの大きい方にプラス1した値とし、この値が2以上のときに行うことを特徴とする請求項1記載のハッシュ表管理装置。.【請求項3】前記バランス処理は、当該二分木構造のトップに至る全ての節について行うことを特徴とする請求項1記載のハッシュ表管理装置。