# SQLite SQLite は組み込み型のリレーショナルDBMSである。*詳説 データベース* 第3章は、スロット化ページにおける削除済み領域の管理例としてSQLiteを挙げる。SQLiteは未使用のセグメントを「フリーブロック(freeblocks)」と呼び、最初のフリーブロックへのポインタをページヘッダに格納する。さらに、使用可能なバイト数の合計をページ内に格納しておくことで、デフラグ後に新しい要素をページへフィットできるかを素早く確認できるようにしている。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] §3.8) ## Bツリーの実装(詳説 データベース 第4章) *詳説 データベース* 第4章は、SQLiteをBツリー実装の具体例として繰り返し引用する。ページヘッダにはセルの数と最右端のポインタが格納される。可変長ペイロードがノードに収まらない場合はオーバーフローページに格納する仕組みを持つ(実装は`balance_deeper`関数)。両側の兄弟ノードが一杯になった場合、1つのノードを半分ずつの2つにスプリットする代わりに、2つのノードを3分の2ずつ満たす3つのノードへスプリットする亜種(`balance-siblings`アルゴリズム)を実装している。単調増加キーが右端に挿入されターゲットノードが一杯なときには、通常のバランシングやスプリットを行わず新しい右端ノードを割り当てる最適化を「クイックバランス」と呼ぶ。データベースで使用されないページのIDはフリーページリスト(フリーリスト)で管理され、トランクページに含まれる連結リストで解放済みページのアドレスを記録する。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]] §4.1, §4.1.5, §4.4, §4.5, §4.7.2) ## 関連 - ソース: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]] - 概念: [[スロット化ページ]] / [[B-Tree]]