「B+木」を公式は使わない — 通称と原典の表記を分ける — データベースの仕組み

リクエストがアプリケーションに届くまで

ブラウザURL入力
DNS名前→IP
ルータ経路選択
ロードバランサ振り分け
Nginx受け口
アプリ処理
DB保存今ここ

ここまでロックが索引レコードに掛かることを見てきました。その「索引」が実際にどんな構造で、公式がそれを何と呼んでいるかを今回扱います。対象は MySQL 8.4 と PostgreSQL 18 です。

まず結論

インデックスの構造は「B+木」と説明されることが多いですが、**MySQL も PostgreSQL も公式文書では B-tree と書きます**。InnoDB は “`InnoDB` indexes are B-tree data structures”、PostgreSQL は “the standard btree (multi-way balanced tree) index data structure” です。

ただし**「B+木ではない」と公式が言っているわけでもありません**。一般に B+木の特徴とされるもの——葉ページにレコードが置かれ、各レベルが相互リンクされる——は、公式の記述からそのまま読み取れます。MySQL の用語集は自ら “may be regarded as variants due to sophistications not present in a classic B-tree design” と書いています。**通称と原典の表記を分けて持つ**のが、ここでの正しい構えです。

? 読む前に予測

MySQL と PostgreSQL の公式文書は、標準的なインデックスの構造を何と表記しているでしょうか。

当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。

抽象原理

公式が使っている語を、まず確かめる

インデックスの構造は「B+木」として説明されることが圧倒的に多いです。ところが公式文書を開くと、その語が出てきません。

MySQL 8.4 はこう書きます。

With the exception of spatial indexes, InnoDB indexes are B-tree data structures. Spatial indexes use R-trees, which are specialized data structures for indexing multi-dimensional data. Index records are stored in the leaf pages of their B-tree or R-tree data structure.

PostgreSQL 18 はこうです。

PostgreSQL includes an implementation of the standard btree (multi-way balanced tree) index data structure.

どちらも B-tree(btree) です。PostgreSQL が索引の種別を並べたページを見ても、現れるのは B-tree だけで、B+tree という表記はありません。さらに PostgreSQL の nbtree の README を機械的に検索すると、B+ は1件もヒットしません(全1,083行)。要約ではなく生のファイルをバイト単位で確認した結果です。

ではその README が自身を何と説明しているか。

Btree Indexing

This directory contains a correct implementation of Lehman and Yao's high-concurrency B-tree management algorithm (P. Lehman and S. Yao, Efficient Locking for Concurrent Operations on B-Trees, ACM Transactions on Database Systems, Vol 6, No. 4, December 1981, pp 650-670)

基準に置いているのは classic B-tree です。

Compared to a classic B-tree, L&Y adds a right-link pointer to each page, to the page's right sibling. It also adds a "high key" to each page, which is an upper bound on the keys that are allowed on that page. These two additions make it possible to detect a concurrent page split

なお参照したのは GitHub 公式ミラーの REL_18_STABLE、つまり PostgreSQL 18 の保守ブランチです。

「公式に無い」と「間違い」は別

ここで結論を急ぐと事故ります。公式は「B+木ではない」と述べていません。 語の選択を説明しているだけです。

MySQL の用語集は、自分が使っている語について自ら注記しています。

The use of the term B-tree is intended as a reference to the general class of index design. B-tree structures used by MySQL storage engines may be regarded as variants due to sophistications not present in a classic B-tree design.

総称として使っている、そして実装は classic B-tree に無い洗練を含む variant と見なしてよい。つまり「公式が B-tree と書いているから classic B-tree そのもの」と読むのも誤りです。

同じページには初学者向けの注意もあります——“Because B-tree nodes can have many children, a B-tree is not the same as a binary tree, which is limited to 2 children per node.” 二分木ではありません。

✓ ここまでの確認

MySQL の用語集は、自ら使っている B-tree という語についてどう注記していますか。

具体実物

通称の側にも根拠がある

では「B+木」という通称は何を指しているのか。一般に B+木の特徴として挙げられるのは、レコードが葉に置かれることと葉(各レベル)が相互にリンクされることです。この2点は、公式の記述からそのまま読み取れます。

MySQL 側。

Index records are stored in the leaf pages of their B-tree or R-tree data structure.

PostgreSQL 側。

PostgreSQL B-Tree indexes are multi-level tree structures, where each level of the tree can be used as a doubly-linked list of pages.

葉ページにレコード、そして各レベルが双方向リンクのリストとして使える。通称が指している性質は、公式の語で確認できます。

だから正確な言い方はこうなります。「公式表記は B-tree。ただし葉ページにレコードを置き、各レベルを相互リンクするなど、一般に B+木と呼ばれる特徴を持つ」。 出典の語と通称を分けて持ち、どちらも否定しない形です。

表記と根拠を分けて整理する表

公式表記        MySQL: "B-tree data structures"
              PostgreSQL: "standard btree (multi-way balanced tree)"
 
公式の自己注記  "general class of index design"
              "may be regarded as variants"
 
通称の根拠      "Index records are stored in the leaf pages"
              "doubly-linked list of pages"
 
通称            B+木 ← 確認した公式ページには現れない

このサイトの別のクイズ(データベース内部のクイズ群)でも「B+木」という語を使っています。それは誤りではなく通称としての用法です。教材側で表記を統一するより、出典の語と通称の関係を理解しておくことの方が実用的です。設計レビューで「公式には B-tree と書かれています」と指摘できるのと、「B+木は間違いです」と断じてしまうのでは、正確さが違います。

✓ ここまでの確認

一般に「B+木の特徴」とされる性質のうち、公式文書の記述から直接読み取れるものはどれですか。

⇄ 2つを見比べる

具体例 A

MySQL — 用語集が自ら variant と認める

MySQL は B-tree という語を使いながら、それが設計クラスの総称であることと、実装が classic B-tree に無い洗練を含むことを用語集で明記しています。つまり「B-tree と書いてあるから教科書の B-tree そのもの」ではありません。空間インデックスだけは R-tree という例外も明示されています。

MySQL 8.4 の記述表

表記      "InnoDB indexes are B-tree data structures"
例外      spatial indexes → R-trees
レコード  "stored in the leaf pages"
 
自己注記  "reference to the general class of index design"
        "may be regarded as variants due to
         sophistications not present in a classic
         B-tree design"

具体例 B

PostgreSQL — 論文名で差分を示す

PostgreSQL は btree と表記し、実装が Lehman & Yao のアルゴリズムであることを README で明言します。classic B-tree との差分も具体的に挙げられており、右リンクと high key の2点が並行するページ分割の検出のために足されたと説明されます。差を隠さないという点で MySQL と同じ構えです。

PostgreSQL の記述表

表記      "standard btree (multi-way balanced tree)"
構造      "doubly-linked list of pages"
 
実装      Lehman and Yao's high-concurrency
        B-tree management algorithm (1981)
 
差分      right-link pointer + "high key"
目的      "to detect a concurrent page split"
 
B+ の出現 README 全1,083行でヒット0件

両者とも公式表記は B-tree ですが、同時に「classic B-tree とは違う」とも書いています。この一見矛盾した書き方から、技術文書の読み方として何を学べるでしょうか。

「何と呼ぶか」と「どういう構造か」は、別々に書かれています。

どちらの方向にも断定しない

この話題は、両方向に極端な結論が出やすい題材です。

「公式が B-tree と書いているから B+木は誤り」——行き過ぎです。公式は否定していません。

「実質 B+木なのだから 公式表記は気にしなくてよい」——これも困ります。引用するときに原文と違う語を書けば、出典を辿った人との間で齟齬が生まれます。

採るべき形は併記です。「公式表記は B-tree(PostgreSQL は btree)。葉ページにレコードを置き各レベルを相互リンクするなど、一般に B+木と呼ばれる特徴を持つ」。 文書を引くときは原文の語、構造を説明するときは根拠となる文を示す——それだけのことです。

実務の場面設計レビューで「ここはB+木だから」と言われたとき

止める必要はありません。通称として広く通じている語です。確かめる価値があるのはその先の主張です。

たとえば「B+木だから範囲検索が速い」という説明は、根拠を公式の記述に置き換えられます。PostgreSQL は各レベルが “doubly-linked list of pages” として使えると書いており、MySQL はレコードが葉ページにあると書いています。リンクを辿って隣へ進める構造だから範囲を順に読める——これなら出典があります。

逆に注意したいのは、構造の話から性能を無条件に導くことです。前回までに見たとおり、索引が使われるかどうかは走査範囲や条件の書き方で変わります。構造が範囲検索に向いているという性質と、あるクエリで実際に索引が使われるかは別の問題です。

文書を書く側に回ったときは、原文の語で引用するのが安全です。「公式は B-tree と表記している」と一行添えておけば、読んだ人が原典を開いたときに迷いません。用語を統一したくなる衝動は、引用の正確さと衝突しがちです。

この章のまとめ

公式表記は MySQL: B-tree / PostgreSQL: btree (multi-way balanced tree)。nbtree README には B+ が1件も無い(全1,083行、バイト単位で確認)。
ただし公式は**「B+木ではない」とは言っていない**。用語集は B-tree を “general class of index design” の総称として使うと明言し、実装を variant と認める。
通称の根拠も公式にある。“Index records are stored in the leaf pages” と “doubly-linked list of pages”。
よって正確な言い方は**「公式表記は B-tree、一般に B+木と呼ばれる特徴を持つ」**の併記。
InnoDB は空間インデックスだけ R-treeという例外あり。B-tree は二分木ではない(“can have many children”)。
PostgreSQL の実装は Lehman and Yao のアルゴリズムで、classic B-tree に right-link pointer と high key を追加。目的は並行ページ分割の検出。

自分の現場で確かめる

読んだだけでは身につきません。手元の環境で実際に見てみてください。

自分が使っているDBの公式文書で `B+` を検索してみる。MySQL のインデックス関連ページと PostgreSQL の btree 関連ページで、ヒットするかどうかを自分で確かめる
チーム内のドキュメントや設計資料で「B+木」と書かれている箇所を探し、出典が付いているかを見る。付いていない場合、それが通称として使われているのか原典の引用なのかを区別する
自分の環境のインデックスが、公式文書のどの語で分類されるかを確認する(SQL なので OS を問わない)。MySQL なら mysql に入り `SHOW INDEX FROM 対象表;` を実行して Index_type 列が BTREE と表示されるかを見る。PostgreSQL なら psql で `\d 対象表` を実行し、インデックスが btree と表示されることを確認する

理解度チェック

読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。

問題 1 / 3正解: 0

「公式が B-tree と書いているのだから、インデックスを B+木と呼ぶのは誤りだ」。この主張の評価はどれですか。

用語集(4語)

B-tree(MySQL の表記): “With the exception of spatial indexes, `InnoDB` indexes are B-tree data structures.” 用語集は総称としての用法を明言する——“The use of the term B-tree is intended as a reference to the general class of index design.”
btree(PostgreSQL の表記): “PostgreSQL includes an implementation of the standard btree (multi-way balanced tree) index data structure.” 構造については “multi-level tree structures, where each level of the tree can be used as a doubly-linked list of pages”。
variant(公式が認める逸脱): “B-tree structures used by MySQL storage engines may be regarded as variants due to sophistications not present in a classic B-tree design.” classic B-tree そのものではないと公式が認めている表現。
Lehman and Yao のアルゴリズム: PostgreSQL の nbtree が実装するもの。“Compared to a classic B-tree, L&Y adds a right-link pointer to each page, to the page's right sibling. It also adds a "high key" to each page”。目的は “to detect a concurrent page split”。

「B+木」を公式は使わない — 通称と原典の表記を分ける