B+木を実装してデータベースとRustのRefCellに詳しくなる
作成日: 2023-05-19
挿入、変更、削除ができるB+木のRust実装です。
$ cargo run run.db
> insert 1 wass [email protected]
Row { id: 1, name: wass, email: [email protected] }
> insert 12 banana [email protected]
Row { id: 12, name: banana, email: [email protected] }
> insert 5 corn [email protected]
Row { id: 5, name: corn, email: [email protected] }
> .btree
Table { root_page_num: 1 }
Node 1 NodeType: Leaf, IsRoot: Yes, Parent: 0 ( NumCells: 3, NextLeaf 0 )
[1] Row { id: 1, name: wass, email: [email protected] }
[5] Row { id: 5, name: corn, email: [email protected] }
[12] Row { id: 12, name: banana, email: [email protected] }
> select 1
Row { id: 1, name: wass, email: [email protected] }
> delete 5
> .btree
Table { root_page_num: 1 }
Node 1 NodeType: Leaf, IsRoot: Yes, Parent: 0 ( NumCells: 3, NextLeaf 0 )
[1] Row { id: 1, name: wass, email: [email protected] }
[12] Row { id: 12, name: banana, email: [email protected] }How Does a Database Work?を読んで、B+木をRustで実装しました。
B+木は多くのリレーショナルデータベースに使われているデータ構造です。値の挿入と削除を対数時間で行える上に、ページキャッシュとの相性が良いという利点があります。
B+木の中身
B+木のノードは葉ノードと内部ノードの2種類があります。葉ノードは行をいくつか保持します。内部ノードは複数のノードを子として持ちます。内部ノードは子ノードのキーの最小値も管理しています。B+木は全体として多分木になります。
Internal A: [3]B [18]C
Internal B: [3]E [9]F [14] G
Leaf E: [3] {id:3 name:Alice} [4] {id:4 name:Bob} [5] {id:5 name:Zeus}
Leaf F: [9] {id:9 name:Charly} [12] {id:12 name:Darlin}
Leaf G: [14] {id:14 name:Eren}
Internal C: [18] G [20] H
Leaf G: [18] {id:18 name:Fran} [id:19 name:Gate}
Leaf H: [20] {id:20 name:Hude} {id:24 name:Idle}B+木として成立するための不変条件があります。
- 全てのノードの子のキーは小さい順に並んでいる。
- 全ての葉ノードは同じ深さである。
- ノードには最小要素数と最大要素数がある。
最大要素数はメモリページ(4096B)に乗る最大値を採用します。最小要素数は最大要素数の半分です。
B+木は追加で葉ノードで次の葉ノードを管理します。
B+木の操作（概略）
葉に挿入するときに最大要素数を超えるならば、葉を分割します。ルートを分割するときは、新しくルートノードを生やします。
葉から削除するときに最小要素数を下回るなら、他の葉から要素を奪うか、他の葉と併合します。ルートが子を1ノードしか持たないときはルートを削除します。
平方分割、バケット法に近いテクニックですね。
Rustでバッファを扱うときのテク
Rustで各ノードを
type Buffer = [0u8; BUFFER_SIZE] という固定長のバッファで表します。バッファを静的な所有権チェッカに囚われずに操作するために、 Rc<RefCell<T>> で囲います。type Buffer = [0u8; BUFFER_SIZE];
type Page = Rc<RefCell<Box<Buffer>>>;ノードを管理するための型を作ります。RefCellから値を長く借りると
BorrowMutErrorが実行時に頻出します。メソッドの中で貸し出しを終えると事故りにくいです。struct Node { page: Page }
impl Node {
fn is_root(&self) -> bool {
let page = self.page.borrow();
// pageを使って処理を書く
}
}ノードの種類ごとに別の型を作ってNodeを埋め込みます。Nodeに個別の処理を実装すると、葉ノードなのに内部ノードのメソッドを呼べてしまうといったことが起こるため嬉しくないです。
struct LeafNode { node: Node }
impl LeafNode {
fn get_num_cells(&self) -> usize { /*略*/ }
}
struct InternalNode { node: Node }
impl InternalNode {
fn get_num_keys(&self) -> usize { /*略*/ }
}ノードの共通の処理を LeafNodeから直接呼びたいのでDerefを実装する
個別のノード処理の型から共通のメソッドを呼びたい、という継承的なことをRustではDerefで行えます。
impl Deref for LeafNode {
type Target = Node;
fn deref(&self) -> &Self::Target {
&self.node
}
}DerefはRustの参照を得る演算子
& をオーバーライドするトレイトです。メソッドを呼び出すときに、型に存在しないメソッドを参照を得てから探す仕組みがあります。これによって、NodeのメソッドをLeafNodeから使えるようになります。leaf.get_num_cells() // <- LeafNodeのメソッド
leaf.is_root() // <- LeafNode型なのにNodeのメソッドを呼べるborrow_mut()の返り値を加工して返すならRefMut::mapを使う
RefCellからborrow_mutで借りた値はRefMut型になっています。RefMut型の一部分をメソッドの外に返すことを考えます。
impl LeafNode {
fn get_head(&self) -> &mut u8 {
&mut self.node.borrow_mut()[0] // <- cannot return value referencing temporary value
}
}このコードはローカルの一時変数RefMutの参照を返すので所有権チェッカに失敗します。RefMutと同じライフタイムで管理される参照を作るには
RefMut::map が使えます。作られたRefMutもnodeと紐付いて管理されます。impl LeafNode {
fn get_head(&self) -> RefMut<u8> {
RefMut::map(self.node.borrow_mut(), |node| &mut [0}]
}
}How Does a Database Work?の注意
2023-05-19、挿入までしか記述されていない現在、B+木の実装が標準的なものではないように感じました。実装したRustのデータ構造と、How Does a Database Work?のデータ構造の違いはリポジトリに記述してあります。