mixi Engineers’ Blog » Inside Tokyo Cabinet その五

先日、MySQL Conferenceという催しに行ってきました。そこでMySQLの開発者のBrian Aker氏およびMichael Widenius氏と話をする機会があったのですが、やっぱしトップランナー達と議論するのは刺激になるなぁと思ったmikioです（その時の資料）。さて、一連の連載も今回が感動の最終回で、TCの性能上の蘊蓄をお届けいたします。 なぜdynamic hashingを使わないか Brianさん達とTCの実装についても少し議論したのですが、その際にdynamic hashingをなぜ使わないのかと問われました。その背景として、TCやQDBMではハッシュのバケット数（＝格納するレコード数を予測してその数倍に設定すべき値）をデータベース作成時に指定しなければならないという問題があります。バケット数が大きすぎると空間効率が劣化し、小さすぎると時間効率が劣化するというトレード

[equinox79]

<mixi Engineers’ Blog » Inside Tokyo Cabinet その五>

[festango]

対障害性。”重要なのは、レコードのエントリポイント（そのレコードに辿り着くポインタ）の更新を、レコードの実体を更新した後に行うということ”

[nilab]

mixi Engineers’ Blog » Inside Tokyo Cabinet その五 : http://alpha.mixi.co.jp/dist/tokyocabinet.ppt

[mogwaing]

少数の巨大なレコードと多数の小さいレコードが混在し、各レコードは高い頻度と偏った確率でサイズが拡張していくという状況で、時間効率が目に見えて落ちない範囲で空間効率を最大化すべく設計

[nobu-q]

Tokyo Cabinetの記事

[monjudoh]

『何で二分探索木を併用しているのかといえば、レコードあたりたった5バイトのオーバーヘッドで手軽に O(log n) を保証できるからです（木が偏らないための工夫もしてあります）。』

[overlast]

一区切りのようなのでブクマ。おもしろかったです。

[kazuhooku]

興味深い

[yohei]

この連載面白いよね

[TAKESAKO]

エクスキューズ特集で最終回【といいつつ何で二分探索木を併用しているのかといえば、レコードあたりたった5バイトのオーバーヘッドで手軽に O(log n) を保証できるからです（木が偏らないための工夫もしてあります）】