著者

平野 泰宏 三浦 史光 武田 英昭

雑誌

全国大会講演論文集

巻号頁・発行日

vol.46, pp.185-186, 1993-03-01

---

データ量nの変化に柔軟に対応でき、検索時間がO(n)となる索引方式であるExtendibIe Hash,Linear Hashなどの動的ハッシュ法が種々提案されている。Extendible Hashはエントリの追加/更新によって溢れたバケットを必ず分割するため、溢れたバケットが分割されるとは限らないLinear Hashよりも安定した検索速度が得られる。しかし、ExtendibIe Hashでは、バケット分割の際に多くのディレクトリエントリを更新する必要があり、クリティカルセクションが長くなるため同時実行性が低下するという欠点があった。本稿では、Extendible Hashを改良し、同時実行性を高めた新しい動的ハッシュ法を提案する。