論文メモ Integrating the UB-Tree into a Database System Kernel
April 29, 2021商用DBMS TransBaseのインデックスをB木からUB木に変え、 多次元アクセス（複数の列の範囲を指定するクエリ）を高速化した。 一見、商用DBMSのインデックスの拡張は複雑かつ高コストのように思える。 UB木は、B木をベースにしたインデックスで、B木のキーの生成とページ分割方法を細工し、範囲クエリを高速化できる。 範囲クエリに向きB木に似たUB木を使うことで、既存のDBMSの範囲クエリを人々の想定よりも簡単に高速化できることを例示した。 また、既存のインデックスの拡張用に提供されたインターフェースを使わず、インデックスを置き換えカーネルにUB木を密結合することで、クエリのオプティマイザを継続して利用できた。
UB木は、Z階数曲線で多次元空間を1次元に写像する。
以下の図は、2次元空間を1次元に写像した様子をあらわす。
(b)のマスには(a)の曲線にそったアドレスがあり、写像後も局所的な位置関係が一定保存されている。
UB木は、レコードであるタプルの値からキー(Z-value)を生成する。
以下のアルゴリズムからなるUBKEYは、Z階数曲線の写像関数であり、キーを生成する。
はじめに、タプルの\(d\)個の要素を\(\texttt{TransformAttribute}\)でビット列に変換する。
変換後も要素の順序関係は保存される。
タプルの要素を\(a\), \(\textit{bitstr}: A \rightarrow\{b\mid b\in[0,1]^{*}\} \)とすると
$$
a_i\le a_j \Leftrightarrow \textit{bitstr}(a_i) \le_{\text{bitstr}}\textit{bitstr}(a_j)
$$
が成立する。
ビット列の先頭は\(0\)で埋められ、連続する末尾の\(0\)はデータサイズを抑えるために省かれる。
下方の2重のfor文は下図のように各ビット列の先頭から順にビットを選び、キーの末尾にビットをたす。
ページ分割とUBKEYによるキーの生成を除けば、挿入、更新、削除のアルゴリズムは、B木と変わらない。 UB木は、範囲クエリと重なる図のZで示されるクラスタの数を減らすために、できるだけクラスタが収まるようにページを分割する。 これを満たすには、分割するページの中で最も短いキー、すなはち末尾の0が最も長いキーを境界として分割するとよい。
タプル\(\textit{ql},\textit{qh}\)で範囲を指定したクエリがあたえられると、\(\textit{ql}\)から\(\textit{ql}\)を含むページの末尾までにある目的のタプルを探す。
これは、以下のアルゴリズムのwhile文の最初の処理にあたる。
\(\texttt{getNextZvalue}\)は、ページの走行を追えたカーソルが次に進むべきキー\(\)を返す。
ページの末尾が下図の点線で囲まれた範囲クエリ内であれば、隣接するページに移動し、先頭から末尾までを調べる。
他方、下図のようにページ末尾が範囲クエリの枠外に出たのならば、下図のように、連続するベージを飛び越え、範囲クエリの境界を含むページにカーソルを移動し、検索を続ける。
論文をこちらからダウンロードできます。 画像は論文から引用されています。