XDDBの軽量化

claude codeにやらせてみた

v2 seedを3bytesで持つ

復元処理の実装がめんどくさかったので24bitのseedを4bytesで持っていたが、上位1byteは必ず0なのでここを詰められる

v3 hpcodeを「直前のレコードのhpcodeからの増分」で持つ

hpcodeでソート済みなのでこれでかなり減らせた

ただしバイト列から直接にぶたんできなくなった

v4計画

hpcodeとseedの対応はほぼ1対1になっているので、これを利用したい

レコード数: 221791

そのうち、2069個は対応する24bit seedが複数存在する

異なるコード数: 219722

対応する24bit seedが1つに定まる: 217682個

対応する24bit seedが2つ存在する: 2011個

対応する24bit seedが3つ存在する: 29個

2011 *2 + 29 *3 = 2069

最小完全ハッシュ（Minimal Perfect Hash / retrieval構造）

乱暴に言えば、置換をハッシュと見なすこと

219,722個の異なるコードに対して Minimal Perfect Hash を作り、seedをそのスロット順に並べる

DBに無いコードを引いた場合: 適当なスロット→無関係なseed→256回生成して全部Check落ち→空結果

トレードオフ

「ソート配列＋二分探索」から「完全ハッシュ＋検証」へのデータ構造変更（V2のビット詰めより大きな作り替え）

MPH/retrieval構造の構築ロジックが必要（C#で実装 or 事前生成してバイナリ同梱）

複数seedコードの扱いを別途用意（スロットに最大3seed、or オーバーフロー表）

CHDのdisplacementテーブルの格納方法

実測したら、d値は大きくても3byteに収まる整数だった

最上位bitが立っていれば次のbyteもこのindexの数値を構成する一部であり、立っていなければ次のindexに移ることを表す

また、「1つのhpcodeに対して複数のseedが対応するケース」に対応するため、それらに該当するhpcodeと対応するseedのペアを別途保持しておく

ここはナイーブにやるしかない