2025/12/12 1:52
Notes on Sorted Data
RSS: https://news.ycombinator.com/rss
要約▶
日本語訳:
要約
バイト単位で値を比較するデータベースは、数値と論理順序を保持しつつコンパクトに保てるエンコーディング方式が必要です。
生のバイトは辞書式に比較されますが、固定幅整数は小さな数ではスペースを無駄にし、ビット順序（エンディアン）問題を起こす可能性があります。可変長整数（例：protobuf）のような連続ビット付きエンコーディングは順序を破壊します。長さプレフィックス方式では、最初に必要最低バイト数を保存し、その後でビッグエンディアン形式の数値を格納することで順序が回復されます。コンパクトな4‑bit プレフィックスは最大15 バイト（124 ビット）まで符号化でき、より大きい値には追加バイトが付加されます。符号付き整数は比較前に再マッピングする必要があります；最小値 (
num ^ MINnum ^ MINMIN任意データに対して長さプレフィックスを使用すると自然な辞書式順序が逆転することがあります（例：
"abcd""4abcd""def""3def"0x00"/""."この記事は読者に追加パターンや修正点を共有してほしいと呼びかけており、さまざまなデータ型や複合構造に対するエンコーディング戦略の継続的改善努力を強調しています。
本文
ストレージシステムでのデータ順序付け
ソート済み状態でデータを格納・比較する必要がある場合、
そのデータの表現方法は極めて重要です。
以下では、順序付きバイト文字列を扱う際に頻繁に発生するパターン（および落とし穴）を整理しています。
1. バイト
- 生のバイトはリテクソグラフィック（「byte‑lexicographical」）で比較されます。
- 多くのデータベース、キー・バリュー ストア、およびその他のシステムではこの比較器が採用されています。
2. 整数
固定幅整数
- 保存は簡単ですが、小さな数値に対してはスペースを浪費します。
- エンディアン の問題：
- ビッグ‑エンディアン（ネットワーク順）：
0x12 0x34 0x56 0x78 - リトル‑エンディアン（x86/ARM）：
0x78 0x56 0x34 0x12
- ビッグ‑エンディアン（ネットワーク順）：
リトル‑エンディアンのバイトを逐次比較しても、数値順序は保たれません。
可変長整数（varint）
典型的な protobuf スタイル varint：
value | encoded | first byte ------------------------------------ 0x10000000 | 0b1_0001_000... | 0x80 ...
- 最上位ビットは継続フラグです。
- しかし最初のバイトは大きさを反映しないため、順序が崩れます。
長さプレフィックス付き（順序付 varint）
number : 0x0B_B8 (3000) bytes : 2 encoded: [0x02, 0x0B, 0xB8]
- 最小バイト数をプレフィックスに格納。
- 残りのバイトはビッグ‑エンディアンで保存。
- 長さが短いほど数値が小さいため、順序が保たれます。
コンパクト 4‑bit 長さプレフィックス
- 必要最小バイト数を算出し、4ビット減算。
- 最初のバイトにそのカウント（4ビット）と数値の上位4ビットを格納。
- 残りのビットは次のバイトへ。
例：
number : 0x0B_B8 (3000) bytes : 2 → 減算1 => 1 first byte: 0x1 << 4 | 0xB = 0x1B encoded : [0x1B, 0xB8]
- 最大で約124‑ビット数をサポート。
- プレフィックスが
の場合、最後のバイトのみ継続ビットを使用し、128‑ビット全体に対応。1111
3. 有符号（負）整数
- 2’s コンプリメントでは最上位ビットが符号として使われます。
- 単純なバイト比較だと
(0xFF) が-1
より大きく扱われてしまいます。0
再マッピング戦略
remapped = original ^ MIN_VALUE // 最小 signed 値で XOR
- これにより、全符号付き範囲が unsigned 範囲へ写像され、順序を保ったまま比較できます。
4. 小数と浮動小数点
IEEE‑754 は符号ビットを最上位に置くため、負の数は正の数よりも大きく見えます（バイト単位で比較した場合）。
ルール
- 正の浮動小数点：
（有符号整数と同様）。num ^ MIN - 負の浮動小数点： 逆順にするため
を行い、次に XOR で正規化。num - MIN
5. 任意データ（文字列・バイト）
- 長さプレフィックスは「長さビットが比較対象になる」問題があります。
"abcd" → [0x04, 'a', 'b', 'c', 'd'] "def" → [0x03, 'd', 'e', 'f'] // 0x04 > 0x03 ⇒ 誤順
- 終端バイト（例：
）を用いてデータを区切ります。0x00- NULL 終端は他の任意バイトより小さいため、自然な順序が保たれます。
- 注意点：データ中に terminator が現れる場合はエスケープが必要です。
6. 複合データ（タプル・構造体）
例：
("12", "34") → [0x31, 0x32, 0x33, 0x34] ("123", "4") → [0x31, 0x32, 0x33, 0x34]
- 両方とも同一のシリアライズを持ち、順序が失われます。
- 要素間に NULL 終端を挿入することで、要素ごとの順序を保証します。
[0x31, 0x32, 0x00, 0x33, 0x34] // ("12", "34") [0x31, 0x32, 0x33, 0x00, 0x34] // ("123", "4")
要約
| データ型 | 順序付け戦略 | 主な注意点 |
|---|---|---|
| バイト | 生のリテクソグラフィック | 単純だがバイト文字列限定 |
| 固定幅整数 | ビッグ‑エンディアン | エンディアンに注意 |
| 可変長整数（protobuf） | なし（順序破綻） | 継続フラグで順序崩壊 |
| 長さプレフィックス付き整数 | プレフィックス + ビッグ‑エンディアン | 順序保持、余分バイト必要 |
| コンパクト4‑bitプレフィックス | プレフィックス＋ビット分割 | スペース節約、範囲制限 |
| 有符号整数 | XOR with MIN | 符号付きを unsigned へマッピング |
| 浮動小数点 | 符号ビット処理 + XOR | 負の値は逆順に変換 |
| 文字列/バイト | NULL 終端 | terminator がデータ中に現れないよう注意 |
| タプル/構造体 | NULL 終端でフィールド区切り | 要素ごとの正確な順序を保証 |
必要に応じて、他のパターンや修正点があればぜひ追加してください！