商用DBMS TransBaseのインデックスをB木からUB木に変え、複数の範囲クエリからなる多次元アクセスを高速化した。 高速な多次元アクセスの拡張を商用DBMSのインデックスに導入することは複雑かつ高コストのように思える。 UB木は、B木をベースにしたインデックスであり、B木のキーの生成とページ分割方法を工夫し、範囲クエリを高速化する。 範囲クエリに向きB木に似たインデックスを使うことで、既存のDBMSの範囲クエリを人々の想定よりも簡単に高速化できることを例示した。 また、既存のインデックスのインターフェースを呼び出す変更ではなく、もとのインデックス自体を変更する当手法には、クエリのオプティマイザを継続して利用できる利点もある。
データ構造は読み込み(Read, R), 更新(Update, U), 所要メモリ容量(Memory, M)にトリレンマを抱え、いかなるデータ構造でも、2つを最適化すると残る1つのオーバヘッドが悪化すると予想した。 Read, Update, Memoryの頭文字から、これをRUM Conjectureと名付けた。
Fractal TreeのamplificationをB+木やLSM Treeと比べて整理した。 Fractal Treeは、B+木のルートと節にバッファをもたせるデータ構造にあたる。 議論になるamplificationはwrite, read, spaceの3つで、write amplificationはアプリケーションの書き込むデータ量に対する実際にストレージに書き込まれたデータ量をさす。 read amplificationはクエリの実行に必要なI/Oの回数、space amplificationは仕組み上避けられない断片化や一時的なデータのコピーをさす。
ソートされたシーケンスの直積を高速に求めるアルゴリズム Double Binary Searchを示した。 2つのシーケンス\(D\), \(Q\)があり、\(\mid D\mid=n\), \(\mid Q\mid=m\), \(n >= m\)であれば、平均と最悪時間計算量が、それぞれ、\(\mathcal{O}(m\log(n/m))\), \(m\)になる。 本アルゴリズムは、Web検索エンジンで大きなシーケンスの直積を高速に求めるために開発された。
LSM-Treeは、検索より挿入や削除が多い用途に向いたインデックス構造であり、例えば履歴テーブルやログの保存につかえる。 メモリにある1つ木とディスク上の1つ以上の木からなり、直近の挿入や削除をメモリの木で管理する。 メモリの木の大きさがしきい値を超えたとき、メモリの木の葉をディスクの木に移す。 移動時は、ディスク上の木の葉とメモリの葉をマージソートの要領でソートし、ソートした葉をディスクの新しい連続領域に書き込む。 連続領域に書き込み、アームの移動やディスクの回転を減らすことで、高速に挿入や削除ができる。 一方、検索速度は、複数の木を探索しなければならないために、1つの木でインデックスを構成するB木に劣る。
Log-structured file system(LFS)は、91年に提唱されたHDD向けのファイルシステムであり、バッファリングした変更をディスクの連続領域に一度に書き込むことで、小さなファイルを大量に高速で書き込める。 また、クラッシュからのリカバリも、ディスク全体ではなくチェックポイント以降に追記された箇所だけを検査すればよいので、高速になる。
ARIES/IMは、B+木への直列化可能性のある並行処理とログ先行書き込み(Write-Ahead Logging, WAL)による復元を実現する。 ARIES/IMのベースには、先行研究のARIESがある。 復元手順はARIESとほとんど変わらない。 キーの参照先にあるデータのレコードとキーを同じロックで保護したり、ロックの代わりにラッチを使ったりすることで、ロックの頻度を下げ、B+木の高速化を実現する。
B木とその派生データ構造のサーベイ論文で、とくにB+木に重点がおかれている。 B+木は、全てのキーを葉におき、葉を隣接リストでつなぐことで、B木が不得手なシーケンシャルなアクセスを改善する。 これにより、定数オーダーの時間と空間計算量で逐次的にキーにアクセスにできる。 ランダムな検索、挿入、削除にかかる時間、空間計算量はB木と変わらない。 以降はB木のデータ構造を前提としてB+木の概要を説明する。B木について知りたい場合は、B木のオリジナル論文の解説記事を見てほしい。
Robust Random Cut Forest(RRCT)はストリームデータ向きの異常検知の手法で、Amazon SageMakerから提供されている。 バッチデータと違い、ストリームデータは新たなデータが随時追加、修正される。 RRCTは、特徴の値でデータを2分するノードからなる木の集合であり、データを追加したときに木の集合であるモデルを大きく複雑するものを異常と判定する。
1972年に発表されたB木のオリジナルの論文。 \(I\)をインデックスの大きさ、\(k\)をハードウェア依存の値とすると、検索、挿入、削除の時間計算量は\(\log_kI\)になる。 ここでのインデックスは、固定長の\((x, \alpha)\)を要素とする連想配列で、最大\(2k\)個のキーを格納できる連続したページ上にある。 \(\alpha\)には、データを保存した1つ以上のレコードへのポインタが格納される。