構造的アルゴリズム
B+Tree
B-Tree の派生型である B+Tree は、個々のキーの検索効率を下げる代わりに、ある範囲のデータをまとめて取得するケースに適した構造を持つ。B-Tree が中間ノードにもデータエントリを保持していたのに対して、B+Tree では末端の葉にのみエントリを保持し、葉は相互にリンクしたリストの構造を持っている。…
R-Tree
R-Tree は深さ平衡木 (depth-balanced tree)。葉ノード
論文翻訳: The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree
空間インデックス (spatial index) のためのアルゴリズム Priority R-Tree (2004) に関する論文。
論文翻訳: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
大量のデータから要素数を推定するアルゴリズム HyperLogLog に関する 2007 年の論文。
Data Encoding
可変長整数エンコーディング
いくつかの可変長整数エンコーディング実装について。このページの話題は任意精度整数演算ではなくデータ圧縮の目的で整数値をエンコーディングする方法である。
基数変換
Base64 はバイナリを 64 種類の文字を使用した文字列に変換する。これは、基数 256 の数列を基数 64 の数列に変換し、それぞれの桁を文字にマッピングすることと等価である。Base58 のような 64 以外の符号化についても、対象とする基数が異なるだけで同じ処理となることが分かるだろう。…