河野真治 @ 琉球大学情報工学です。

In article <ull4l3kjw.fsf@katsu.watanabe.name>, WATANABE Katsuhiro <katsu@watanabe.name> writes
> あまりのフォローアップの遅さが議論の妨げになっていたら
> ごめんなさい。少し勉強して出直してきました。

つうか、レベル高すぎ...

>     sdbm : 狭義の Dynamic hashing [DYNAMIC]
>     gdbm : Extendible hashing [INDEX]
>     Berkeley DB : Linear hashing [INDEX]
> なお、Linear hashing には興味深い別名があって、
> Incremental hashing とも呼ばれます。

おぉ。僕も勉強しないとあかんな。

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

なるほどね。微妙に、B-Tree 的ですね。多段の表にするんだ
ろうな。

In article <ufyut3jss.fsf@katsu.watanabe.name>,WATANABE Katsuhiro <katsu@watanabe.name> writes
> グラフでは、[階段]状に急に遅くなっている部分は見られません。
> これは、平均性能（＝多数の insert の累積時間）を重視する
> タイプの応用なら、問題は小さいことを意味しています。

ふむふむ。

> 対比して、key 数が大きくなるにつれグラフの[傾斜]すなわち
> １回１回の insert の性能が悪化します。これは、rehash の
> ような全域的再計算によるものではないにもかかわらず、
> 破綻というのにふさわしい状況(傾きが急になる一方)です。
> このとき、loadavg は下がり、ページングではない種類の
> ディスクアクセスばかりをやる状況になっていました。
> しかし、この性能悪化の本質を私は絞れていません。

DB は、normal file ですか? Unix FS 上に作っちゃうと、
i-node 自体が B-Tree 的な構造になるので、hash と干渉
するかも知れません。

> 注：
> この記事でいう Berkeley DB は、FreeBSD や NetBSD の
> libc のものです。4.4BSD-Lite に含まれていたものの子孫で、
> 最近はあまり保守されてないように見えます。バージョン4系列
> (sleepycat が保守していて Linux のディストリビューション
> でよく見るもの)は現在も進化中で、状況が違うかもしれません。

Berkeley DB って、レコードの大きさは32bit 表現なんですね。
64bit 対応のが欲しいんだけど... PostgreSQL は出来るとか
聞きましたが、どうなんだろう?

---
Shinji KONO @ Information Engineering, University of the Ryukyus
河野真治 @ 琉球大学工学部情報工学科