cstack

SQLiteクローンをCで自作して、B+Treeの仕組みを理解する 1. はじめに 背景 私はiOSアプリ開発を専門としていますが、最近はバックエンドの開発にも挑戦しており、その中でDB設計も担当するようになりました。バックエンド開発では、日常的にレコードのINSERTやSELECTをしています。しかし、その裏でディスクとメモリがどのように協調して動いているのかは、ブラックボックスのまま扱っていました。 また、検索が遅かったAPIがインデックスを張っただけで高速になった事例を見て、データベースやインデックスの仕組みを正しく理解したいと思うようになりました。仕組みがわかっていれば、インデックス設計や主キーの選び方といった実務の判断の際に、AI任せにせずに、自分で根拠を持って判断できると考えたためです。 DB設計について書籍を読んで学んではいましたが、読むだけではなぜそうなるのかまでは腹落ちしない部分がありました。そこで、より深く理解するためのいい方法がないかと思っていました。そんなときに参加したiOSDCで、「Swiftで作って学ぼう！データベース自作入門」という発表の中で、今回取り組んだチュートリアルが紹介されていました。内容はまさに自分がやりたかったものだったので、実装してみることにしました(チュートリアルと同じC言語を使いました)。 本記事では、SQLiteのクローンをC言語で一から実装するチュートリアルに取り組み、特に面白かったB+Treeについて解説します。 チュートリアルの紹介 C言語でSQLiteのクローンを一から実装する「Let's Build a Simple Database」というチュートリアルです。 cstack.github.io cstack/db_tutorial 実装した内容 SQLiteのクローンと聞くと、高機能なものを想像するかもしれませんが、機能は限定されています。 REPL(プロンプト受付)とトークナイズ・構文解析 ページ単位でディスクとやり取りするPager B+Tree(Leaf Node / Internal Nodeの探索と分割ロジック) スキーマは id, username, email の3カラム固定 insert と select のみ可能 データの削除やトランザクションなし B-TreeとB+Treeについて チュートリアルの章タイトルは「Introduction to the B-Tree」ですが、実装するのは正確にはB+Treeです。SQLiteはテーブルをB+Tree、インデックスをB-Treeで保存しており、チュートリアルではテーブルだけを実装するためです。チュートリアルの本文でも次のように区別されています。 The picture from above is a B-Tree, which SQLite uses to store indexes. To store tables, SQLites uses a variation called a B+ tree. 2. なぜB+Treeなのか 配列 チュートリアルの前半では、行をページに先頭から順番に詰めていくだけの、配列のような構造でテーブルを保存していました。この方法だと、特定の id の行を探すには先頭から全行を走査するしかなく、検索にO(N)かかります。 配列を id 順にソートしておけば、二分探索でO(logN)で検索できます。しかし今度は、途中に挿入するたびに後ろのデータをすべてずらす必要があり、挿入がO(N)になります。 二分探索木 検索も挿入もO(logN)で行いたいときに、まず思いつくのが二分探索木です。各ノードが1つのキーを持ち、それより小さいキーは左の子、大きいキーは右の子に置きます。木がバランスしていれば高さはlogN程度になり、検索も挿入もO(logN)で済みます。 ところが、DBでよく使われる AUTO_INCREMENT のような連番のidを主キーにすると、キーは常に昇順で挿入されます。素朴な二分探索木に昇順で挿入すると、新しいキーは毎回いちばん右に追加され、木は一方向に伸びていきます。 これは実質的に連結リストで、検索はO(N)に逆戻りしてしまいます。 平衡二分探索木 この偏りは、赤黒木やAVL木のような平衡二分探索木を使えば解決できます。挿入のたびに回転操作で木を組み替え、高さを常にO(logN)に保ってくれます。 しかし、平衡二分探索木ではデータがメモリにあって高速にアクセスできる場合はいいのですが、データをHDDやSSDに配置している場合は、ディスクの読み込みがボトルネックになります。二分探索木は1ノードに1キーしか持たない構造なので、比較を1回するたびに次のノードを読み込む必要があります。ノードがディスク上にあると、比較を1回するたびにディスクI/Oが1回発生します。100万行なら高さは log2(1,000,000) ≒ 20 なので、1回の検索で最大20回のディスクI/Oが発生します。 これがなぜ問題なのかは、ディスクI/Oの特性を見るとわかります。 ディスクI/Oの2つの特性 1つ目は、メモリに比べて遅いことです。Jeff Deanによる有名な目安(Latency Numbers Every Programmer Should Know、2012年ごろの値)では、メインメモリの参照が約100nsなのに対し、SSDから4KBをランダムに読むのは約150µsと、1000倍以上の差があります。現在のSSDではこれよりも速くなっていますが、それでもメモリとは数百倍の差があります。そのため、ディスク上のデータ構造では、比較の回数だけでなく、ディスクI/Oの回数が性能に影響します。 2つ目は、決まった単位でまとめてしか読み書きできないことです。OSやファイルシステムは、ディスクを4KB程度のブロック単位で読み書きします(HDDのセクタは今は4KBが主流で、SSDの内部の読み書き単位は4〜16KB程度)。そのため、100バイトだけ欲しくても、実際には最低でも4KBがまとめて読み込まれます。 この2つを踏まえると、二分探索木に無駄があることがわかります。キーと左右の子へのポインタだけを持つノードなら、大きさは十数バイトです。遅いディスクI/Oで4KBを読み込んでも、そのうち使うのはノード1つ分の十数バイトだけで、残りは捨ててしまいます。しかも、それを比較のたびに繰り返します。 つまり、ディスク上のデータ構造は、この読み書きの単位に合わせて設計する必要があります。そこで登場するのが、1回の読み込みで得られる4KBを無駄なく使えるように設計されたB+Treeです。 B+Tree B+Treeも平衡木の一種です。挿入時にノードを分割することで、ルートからどのLeafまでの深さも常に同じに保ちます。そのため、連番のidを挿入し続けても偏らず、O(logN)で検索できます。 二分探索木との大きな違いは、1ノードに多数のキーを並べて持つことです。4KB単位の読み込みに合わせて、1ノードを1ページ(4KB)とし、近い範囲のキーをまとめて詰め込みます。今回の実装のページレイアウトでは、次のようになります。 ヘッダ: 14バイト 子ノードへのポインタ: 4バイト キー: 4バイト 1キーあたり、子ポインタとキーの組で8バイトを使うので、Internalノード1つに最大510個(= (4096 - 14) / 8)のキー、つまり511個の子を持てる計算になります(子はキーより1つ多いため)。 (ただし、チュートリアルのコードではテストしやすいように、最大3キーに制限されています) 図にすると、次のような形です。図では1ノードにキーを2個ずつしか描いていませんが、実際にはInternalノードには数百個のキー、Leafノードには13行まで並びます。 Internalノードは、行データを持たず、「どの子に進めばいいか」の目印になるキーだけを持ちます。各キーは「その子以下に含まれる最大のキー」で、最後のキーより大きいものは一番右の子に進みます。たとえば2段目の左のInternalノード [50 | 80] では、50以下なら左、50より大きく80以下なら真ん中、80より大きければ右の子に進みます。 Leafノードは、キーと行データの組をキーの順に並べて持ちます。どのLeafもルートからの深さが同じです。 Leaf同士は右隣へのポインタ(矢印)でつながっているので、範囲検索や全件の走査ではLeafだけを左から順にたどれます。 たとえば id = 90 を探す場合は、まずルートのページを読み、90 <= 100 なので左の子に進みます。次にInternalノードのページを読み、80 < 90 なので一番右の子に進みます。最後にLeafのページを読み、その中から 90 を探します。ディスクから読むのは、最大でも木の段数と同じ3ページだけです。 1回のディスクI/Oでこのページを読み込めば、そのページ内での二分探索(511個の子から進む先を選ぶので log2(511) ≒ 9 回の比較)はメモリ上だけで完結します。つまり、二分探索の何ステップ分かを1回のI/Oでまとめて済ませることができます。 木の高さの試算 ディスク上のデータ構造では、木を1段たどるごとに最大1回のページ読み込み(ディスクI/O)が発生します。ここでは、ページがキャッシュされていない場合を考えます。100万行を保存したときの木の高さで比べてみます。B+Treeは1ページにできるだけ多くの子を詰め込むことで、木を低く保ち、I/O回数を最小にしていることがわかります。 構造 1ノードの子の数 100万行での高さ(≒ ディスクI/Oの回数) 平衡二分探索木 2 約20段 B+Tree 511 3段 すべてのノードが満杯だと仮定すると、B+TreeのLeafには13行しか入らないので、100万行には 1,000,000 / 13 ≒ 7.7万 枚のLeafが必要です。Internalノード2段で 511 × 511 ≒ 26万 枚のLeafを指せるので、Leafを含めて3段になります。(ただし、今回のチュートリアルの実装では分割時にノードを半分ずつに分けるので、各ノードは半分程度しか埋まりません。) 一般にB+Treeのメリットとして、木の高さが低くなることが挙げられます。ただ、学習中に疑問に思ったのが、「子を多く持てば木は低くなるが、そのぶん1つのノードの中で進む子を探すのに時間がかかり、トータルの計算量は増えてしまうのではないか？」という点です。結論からいうと、計算量は二分探索木と同じO(logN)のままです。 まず、ノード内のキーはソートされて並んでいるので、進む子は二分探索で決められます。チュートリアルのコードでも、Internalノードで進む子を選ぶ処理(internal_node_find_child)と、Leaf内でキーを探す処理(leaf_node_find)は二分探索で実装されています。 1ノードの子の数をmとすると、木の高さは \log_m N、1ノード内の比較回数は \log_2 m なので、検索全体の比較回数は次のようになります。 \log_m N \times \log_2 m ここで、底の変換公式 \log_m N = \dfrac{\log_2 N}{\log_2 m} を使うと、 \log_m N \times \log_2 m = \frac{\log_2 N}{\log_2 m} \times \log_2 m = \log_2 N となります。つまり、子の数をいくら増やしても、検索全体の比較回数は二分探索木と同じO(logN)のままです。変わるのは、その比較を何回のディスクI/Oに分けて行うかだけです。 ページサイズはDBによって異なる 今回の実装では、1ページを4096バイト(4KB)にしています。これは、多くのOSの仮想メモリのページサイズや、ファイルシステムのブロックサイズと同じ値です。前述のとおり、ディスクはこの単位でまとめて読み書きされるので、B+Treeのノードもこのページ1枚に対応させています。 ただし、ページサイズはDBによって異なります。 DB デフォルトのページサイズ 変更できるか SQLite 4KB(3.12.0以降。それ以前は1KB) 512B〜64KBの2の累乗から選べます。PRAGMA page_size で、DB作成前か VACUUM 時に設定します MySQL(InnoDB) 16KB innodb_page_size で4 / 8 / 16 / 32 / 64KBから選べます。インスタンスの初期化時にしか設定できません ページを大きくすると、1ページに入るキーが増えて木が低くなり、範囲検索でまとめて読むときにも有利です。一方で、1行だけ読み書きするときの無駄は増えます。それぞれのデフォルト値について、公式ドキュメントでは次のように説明されています。 SQLite：2003年にファイルフォーマットを設計したときから、デフォルトは1KBでした。当時としては妥当な選択でしたが、「現代のハードウェアでは4KBの方が速く、よい選択である」として、3.12.0(2016年)で4KBに変更されました(The Default Page Size Change of SQLite 3.12.0)。 MySQL(InnoDB)：デフォルトの16KB以上は幅広いワークロードに適しており、特にテーブルスキャンや一括更新を伴う処理に向いているとされています。一方で、1ページに多くの行が入ると競合が起きやすいため、小さな書き込みが多いOLTPでは小さいページの方が効率的な場合があります。また、ブロックサイズの小さいSSDでも、小さいページの方が効率的な場合があるとされています(innodb_page_size)。 次章では、実装したコードを見ながら、ここまでの仕組みがどう実装されているかを見ていきます。 3. B+Treeの実装 ノードのレイアウト 各ノードは1ページ(4096バイト)で、先頭に共通ヘッダを持ちます(LeafノードとInternalノードで共通)。 Common header (6 bytes) +-----------+---------+----------------+ | node_type | is_root | parent_pointer | | 1 byte | 1 byte | 4 bytes | +-----------+---------+----------------+ Leafノードは、キーと行データ(value)の組をcellとして並べます。 Leaf node (4096 bytes) +---------------+-----------+-----------+--------+--------+-----+------------+ | common header | num_cells | next_leaf | cell 0 | cell 1 | ... | free space | | (6) | (4) | (4) | (297) | (297) | | | +---------------+-----------+-----------+--------+--------+-----+------------+ cell = key (4 bytes) + value = row (293 bytes) 1行は id(4) + username(33) + email(256) = 293バイトなので、1 cellは297バイトです。ヘッダを除いた4082バイトに入るのは 4082 / 297 = 13 cellで、1つのLeafには13行まで入ります。今回の実装での行の定義は次のとおりです。 #define COLUMN_USERNAME_SIZE 32 #define COLUMN_EMAIL_SIZE 255 typedef struct { uint32_t id; char username[COLUMN_USERNAME_SIZE + 1]; char email[COLUMN_EMAIL_SIZE + 1]; } Row; next_leaf は右隣のLeafのページ番号です。Leaf同士をつないでおくことで、select で全件を読むときに、木を上り下りせずLeafだけを順にたどれます。 Internalノードは、子ポインタとキーの組をcellとして並べます。 Internal node (4096 bytes) +---------------+----------+-------------+---------+---------+-----+ | common header | num_keys | right_child | child 0 | key 0 | ... | | (6) | (4) | (4) | (4) | (4) | | +---------------+----------+-------------+---------+---------+-----+ cell = child (4 bytes) + key (4 bytes) = 8 bytes key i は child i 以下に含まれる最大のキーです。最後のキーより大きいものは一番右の子をたどります。子ポインタはキーより1つ多いので、一番右の子はヘッダの right_child に持たせています。 探索では、Internalノードで二分探索して進む子を決め、Leafにたどり着いたらLeaf内でも二分探索して目的のcellを見つけます。 ノードの分割 Leafが満杯(13 cell)のときにさらに挿入すると、ノードを分割します。 既存の13 cellと新しい1 cellの計14 cellを、左右に7つずつ分けます。 右半分は新しく確保したページ(新しいLeaf)に移します。 親のInternalノードに、新しいLeafへの子ポインタとキーを追加します。また、左側に残ったLeafは最大キーが変わるので、親が持つそのLeafのキーも更新します。 親も満杯なら、親も同じように分割します。これがルートまで連鎖することがあります。 分割したのがルートだった場合は、新しいルートを作り、分割した2つのノードをその子にします。 B+Treeが高くなるのは、この5のルートの分割のときだけです。木は下に伸びるのではなく、上に1段ずつ伸びるので、どのLeafもルートからの深さが常に同じに保たれます。 4. まとめ SQLiteのクローンを自作することで、ディスクを4KBのページ単位で扱い、B+Treeが1ノード = 1ページとしてキーを整理している、という仕組みを自分の手で確かめられました。特に、B+Treeが1ページに多くのキーを詰め込むことで1ノードの子の数(ファンアウト)を大きくし、ディスクI/Oの回数を抑えている点は、実装して数字を計算してみて初めて腹落ちしました。 実務との関係でいうと、「UUIDv4を主キーにすると遅い」という話も、以前はなんとなく「ランダムだと遅いんだな」という程度の理解でした。今回の学習で、ランダムなキーでは挿入先のLeafが毎回ばらばらになり、あちこちのページで分割が起きたり、キャッシュにないページを読み込んだりすることになるからだ、と一段高い解像度で説明できるようになりました。 参考 Let's Build a Simple Database cstack/db_tutorial SQLite Database File Format SQLite PRAGMA page_size The Default Page Size Change of SQLite 3.12.0 MySQL 8.4 Reference Manual: innodb_page_size Latency Numbers Every Programmer Should Know