dbm ファミリの表の拡張についてです。

dbm ファイルの大きさの変化や、Berkeley DB のバージョン間の
差異については、私はよくわかりません。


記事 <YAS.05Jul13183806@kirk.is.tsukuba.ac.jp> で
yas@is.tsukuba.ac.jp (Yasushi Shinjo) さんいはく

> > 多分古い dbm, ndbm も含め、表の拡張は pair の詰った bucket
> > を "split" することで行います。address 範囲が増える分は、
> > hash 関数自体は変えず addressing に用いる bit 数を増やして
> > 対応します。最初は LSB 4bit を使い、混んできたら 5bit を
> > 使うという具合です。今まで 1101 の bucket に入っていた
> > データは、01101 と 11101 の bucket へと split して振り分け
> > られます。
> 

> 検索の時ですが、最大が 4 ビットから 5ビットになったすると、
> まず、5ビットと思って探してみつかればよし、みつからない（ブ
> ロックがない）と、4ビットにしてさがす、それでもなければ、さ
> らに３ビット、２ビットと減らしていくと。

探し方の部分はバリエーションになっていて色々な戦略があります。

bucket をアドレスする hash 値の bit 数が混在してもよいように、
狭義 Dynamic は trie 辞書、Extensible は一段階の間接表を
利用します。Linear では、split する順番を決めてしまい、split
済みのものとまだのものが表中で仕切りを隔てて区分されるように
工夫します。


[狭義の Dynamic hashing]
初期状態として bucket がどれも 4bit で指されてるとしましょう。
準備として、高さ 4+1 の完全な二分木を作ります。根から葉へと
向かう path に沿って {0,1} で印をつけ、これを hash 値の LSB 側
から順の bit pattern と解釈します。つまり、根直下の節は bit0、
葉は bit3 です。例えば 1101 の周辺はこんな感じ：

+-0- 
|              +-0001
|        +-001-+
+        |     +-1001
|   +-01-+
|   |    |     +-0101
|   |    +-101-+
+-1-+          +-1101
    |

各葉から対応する bucket への pointer を埋め込めば、hash 値の
bit pattern から bucket への対応が自明に完成します。

今、hash 値の 1101 に対応する bucket[1101] を split し、
bucket[01101] と bukect[11101] に分けたとしましょう。このとき、
木の方でも 1101 の葉で分岐を起します。新たな葉は 01101, 11101
とみなせます。これらに bucket[01101] と bucket[11101] への
pointer を埋め込みます。

こうして成長する木をたどれば、hash 値の bit 数が場所によって
違っていても、常に bucket を正しくアドレスできます。


[Extendible hashing]
ほとんどの bucket は 4bit で指されているけれど、例外的に
...1101 の部分だけ 5bit で bucket[01101] とbucket[11101] に
split されているという状態を考えましょう。

大きいほうの bit 数 5 に都合を合わせて、大きさ 2^5=32 の配列
directory を作り、これを bucket への間接表とします。間接表の
中身はどうするかというと、まず split されている部分については
  directory[01101] -> bucket[01101]
  directory[11101] -> bucket[11101]
のように直に指し示すようにします。そして、その他ほとんどの
split されていない部分については、たとえば 0000 についてなら
  directory[00000] -> bucket[0000]
  directory[10000] -> bucket[0000]
のように 4bit の bucket[0000] を重複して指させます。この間接表
を経由すれば、常に 5bit 固定で楽に bucket をアドレスできます。

もし将来 bucket[0000] が split されても、directory[00000] と
directory[10000] だけをいじればよいです。

さらに将来 6bit 分必要な部分が出たら、このときは directory の
大きさを 64に倍増させて再構成する羽目になります。しかしこの
作業は結局 bucket への pointer のコピーの繰り返しであり、多少
重いながらも致命的ではありません。


[Linear hashing]
ある仕切りの値を境として、それより hash 値が小さい方の bucket
は split し、大きい方の bucket は split しないよう区分したら
どうでしょうか。大小比較によって 4bit, 5bitを切り替えればよい
ので、hash 値から trie 辞書や間接表を引く手間が生じません。

初期状態として bucket がどれも 4bit で指されてるとしましょう。
2^4=16 個の bucket を、hash 値の昇順に配列の形で並べます。
hash 表の混み具合に応じて適当な時期に split しますが、好き勝手
な場所を split するのではなく、配列の先頭から順に行うように
固定します。split で bucket が増える分は最後尾に連結します。

 0000  0001  0010  ...  1111
  |
  +-----------------------------+  0000を00000,10000にsplit
  V                             V
00000  0001  0010  ...  1111  10000
        |
        +-----------------------------+ 0001をsplit
        V                             V
00000 00001  0010  ...  1111  10000 10001
              |
         次のsplit対象はここ

このように整列し、4bit, 5bit 部分がバラバラではなく塊で区分け
できれば、アクセスすべき bucket は次のように決まります。

    h = hash 値;
    q = 最後に split した場所;  // 上図 3 段目の状態では 0001
    n = (h の LSB 4bit 分だけ);
    if (n > q) {
        未 split の領域なので bucket[n] をアクセスする;
    } else {
        bucket[h の LSB 5bit] をアクセスする;
    }

一段階の条件判断が入っているのみで、木や間接表などの二次的な
データ構造の助けを借りていないことに注意してください。

このアルゴリズムでは、表の混んでいる部分を恣意的に split する
ことはできません。安定して動作するためには、いつ・どの程度
split を進めるかの schedule も考える必要があります。

-- 
渡邊克宏 http://katsu.watanabe.name

-- 
渡邊克宏 http://katsu.watanabe.name