新城＠筑波大学情報です。こんにちは。
いい記事は、いつ投稿されてもいいですね。

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

size.png で、横軸にキーの数、縦軸にファイルの大きさをとると、
２倍になっている所がありますよね。この時は、ファイル全体をど
んと２倍にするというよりは、キーのあるブロックだけとりあえず
２倍にするのでしょうか。

検索の時ですが、最大が 4 ビットから 5ビットになったすると、
まず、5ビットと思って探してみつかればよし、みつからない（ブ
ロックがない）と、4ビットにしてさがす、それでもなければ、さ
らに３ビット、２ビットと減らしていくと。ブロックの存在確認は
少し無駄な気もするけど、それはまた別途なにかやっているのです
かね。

In article <ufyut3jss.fsf@katsu.watanabe.name>
        WATANABE Katsuhiro <katsu@watanabe.name> writes:
> 別途 insert １回毎の時間の最大値も監視してみています。
> 遅い回というのは間歇的にやってくるのですが、それも
> Berkeley DB では1〜2秒、gdbm だと 2〜3秒でした
> (Pentium 1GHz)。応用によっては許せる範囲でしょう。

この1〜2秒は、Berkeley DB のせいじゃないかもしれませんよ。OS 
のファイル・システムのせいかもしれません。FreeBSD でなくて、
Linux ですが、大量データを書込んでいると、時々、数秒止まりま
す。あれやめて欲しいんだけど。

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

グラフには、Berkeley DB 1.8.5 と書いてありますね。今新しいの
は、4.3 だから、番号だけはだいぶちがいます。時々、ライブラリ
で 1 用と 2 以降用に分かれていますが、あれは API の違いなん
ですか？

API が違っても、内部のアルゴリズムはあんまり変ってないんじゃ
ないかな。

API が同じなら、Berkeley DB 2/3/4 の違いって何なんでしょう？

In article <3992098news.pl@rananim.ie.u-ryukyu.ac.jp>
        kono@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> なるほどね。微妙に、B-Tree 的ですね。多段の表にするんだ
> ろうな。

ビットが長い所から見れば、多段の表にはならないと思いました。
ビットを減らしていくので、バイナリサーチには違いないけれど。

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

OS のバッファ・キャッシュとの競合が大きいと思います。この時
代から。

M.Stonebraker: "Operating System Support for Database
Management", Communications of the ACM, Vol.24, No.7,
(1981).

この時代のイメージは、今でもけっこう残っていて、Oracle で 
raw disk が常識かと思っていたら、Oracle でもファイル・システ
ムを使うのもけっこう多いみたいね。

In article <upstopw9o.fsf@katsu.watanabe.name>
        WATANABE Katsuhiro <katsu@watanabe.name> writes:
> いまここで議論している大規模な hash 表の扱いなんてものは、
> DB 屋さんが 20 年ぐらい前にさんざんやったとの追体験なの
> でしょうか。

DB屋さんは、そう見えるでしょうね。実際には、回りの情況まで含
めて考えると、考えるべき要素が増えていて、話が難しんだけど。

＼＼　新城　靖　（しんじょう　やすし）　＼＼
＼＼　筑波大学　電子・情報　　　　　　　＼＼