Bツリーとデータベースインデックス

 (planetscale.com)
41 ポイント 投稿者 GN⁺ 2024-09-11 | 1件のコメント | WhatsAppで共有

B-treeとは何か？

  • B-treeは多くのソフトウェア、特にデータベース管理システム（DBMS）の基盤となる役割を果たす

  • MySQL、Postgres、MongoDB、Dynamo などは、インデックスを通じて効率的なデータ検索を行うために B-tree に依存している

  • B-tree と B+tree がどのように動作するのか、なぜデータベースがインデックスにこれを使うのか、そして UUID を主キーに使うことが悪い考えかもしれない理由を学ぶ

  • B-tree は、キー と 値 として知られるデータの組を、プログラマが木に似た構造と呼ぶものに保存する

  • B-tree は ノード（四角形）と 子ポインタ（ノードをつなぐ線）で構成される

  • 最上位ノードを ルートノード、最下層のノードを リーフノード、それ以外のすべてのノードを 内部ノード と呼ぶ

  • 以下が B-tree の定義である:

    • 各ノードは N 個のキー/値の組を保存する（ここで N は 1 より大きく K 以下）
    • 各内部ノードは少なくとも N/2 個のキー/値の組を持つ（内部ノードはリーフでもルートでもないノード）
    • 各ノードには N+1 個の子がある
    • ルートノードは唯一のノードでない限り、少なくとも 1 つの値と 2 つの子を持つ
    • すべてのリーフは同じレベルにある

  • B-tree のもう 1 つの重要な特徴は整列である。各ノード内では要素が順序どおりに維持される

  • この整列性により、キー検索を非常に効率よく行える。検索はルートノードから始まり、次のように進む:

    1. 探しているキーがノードに含まれているか確認する
    2. なければ、追加する場合にキーが挿入される位置をノード内で探す
    3. この時点で 子ポインタ をたどって次のレベルへ移動し、同じ処理を繰り返す

  • この方法で検索すると、1 つのキーを探すために木の各レベルで 1 つ のノードだけを訪問すればよい

  • B-tree は、非常に大量 のデータを扱い、しかも長期保存（ディスク）に永続化する必要がある場合にうまく機能するよう特別に設計されている。その理由は、各ノードが固定バイト数を使うためである

  • B-tree において各ノードが格納できる値の数は、それぞれに割り当てられたバイト数と、各キー/値の組が消費するバイト数によって決まる

B+tree（データベース向けに最適化）

  • B+tree は B-tree に似ているが、次のルールが変更されている:
    • キー/値の組はリーフノードにのみ保存される
    • 非リーフノードはキーに関連づけられた子ポインタだけを保存する
  • MySQL インデックスにおける B+tree 実装には、さらに 2 つの特有のルールがある:
    • 非リーフノードは N+1 ではなく N 個の子ポインタを保存する
    • すべてのノードには「次」と「前」のポインタも含まれ、木の各レベルが双方向リンクリストとしても機能できる
  • B+tree がデータベースにより適している理由は 2 つある:
    1. 内部ノードは値を保存する必要がないため、内部ノードあたりにより多くのキーを入れられる。これは木の深さを減らす助けになる
    2. すべての 値 は同じレベルに保存され、最下層のリンクリストを通じて順序どおりに走査できる

MySQL における B+tree の使い方

  • MySQL は複数のストレージエンジンをサポートしており、最も一般的に使われるエンジンは B+tree に大きく依存する InnoDB である
  • 実際、InnoDB はテーブルの主キーをツリーのキーとして使い、すべてのテーブルデータ を B+tree に保存するほど強く依存している
  • 新しい InnoDB テーブルを作成するたびに、主キーを指定する必要がある
  • MySQL は新しい各テーブルについて B+tree を作成し、主キーに設定された値がツリーのキーになる。値は各行の残りの列の値であり、リーフノードにのみ保存される
  • この B+tree の各ノードサイズはデフォルトで 16k に設定されている
  • MySQL がデータ片（キー、値など）にアクセスする必要があるたびに、他のキーや値が不要でも、関連するページ全体（B+tree ノード）をディスクから読み込む
  • InnoDB テーブルにはセカンダリインデックスを作成することも一般的である。各セカンダリインデックスごとに追加の永続 B+tree が構成され、キーはユーザーがインデックスを構築することを選んだ列、値は関連する行の 主キー である

主キー選択: 挿入

  • テーブルデータが B+tree にどのように配置されるかは選択したキーによって異なるため、PRIMARY KEY の選択はテーブル内のすべてのデータのディスクレイアウトに影響を与える
  • 主キーとして一般的に選ばれる 2 つは次のとおり:
    • 整数シーケンス（BIGINT UNSIGNED AUTO_INCREMENT など）
    • UUID（バージョンは複数ある）
  • UUIDv4 主キーを使う場合の結果を考えると、挿入時には:
    1. 挿入のために訪問されるノードを事前に予測できない
    2. 挿入対象となるリーフノードを予測できない
    3. リーフの 値 は整列しない
  • 多くの挿入の過程でツリー内の多くのノード（ページ）を訪問しなければならないため、1 と 2 の問題が発生する。このような過剰な読み書きは性能低下につながる
  • BIGINT UNSIGNED AUTO_INCREMENT を主キーとして使う場合:
    1. 新しい値を挿入するときは常に最も右側の経路をたどる
    2. リーフはツリーの右端にのみ追加される
    3. リーフレベルではデータは挿入順に整列する
  • 1 と 2 により、連続して発生する多くの挿入は同じページ経路を再訪することになるため、多数のキー/値の組を挿入するときの I/O リクエストが減る

主キー選択: 順序どおりのデータ読み取り

  • データベースでは、時系列順にデータを取得することがよくある
  • UUIDv4 を主キーに使うと、検索結果の値シーケンスが複数の非連続なリーフノードに分散する
  • 連続して挿入された値を探す場合、検索結果を含むすべてのページは互いに隣接することになる。複数行を取得するとき、それらが単一ページ内で隣接していることもある
  • このようなクエリパターンでは、順次主キーを使うことで読み取るべきページ数を減らせる

主キー選択: サイズ

  • 主キーのサイズも重要な検討事項である。主キーは常に次を満たす必要がある:
    1. 枯渇しないよう十分に大きいこと
    2. 過剰な保存領域を使わないよう十分に小さいこと
  • 整数シーケンスの場合、小さめのテーブルなら MEDIUMINT（1600万個の一意値）や INT（40億個の一意値）を使える
  • 大きなテーブルでは BIGINT を使って安全性を確保する（18京超の値を取れる）。BIGINT は 64 ビット（8 バイト）である
  • UUID は一般に 128 ビット（16 バイト）で、MySQL の最大整数型の 2 倍である
  • B+tree ノードは固定サイズなので、BIGINT を使えば UUID よりノードあたりに多くのキーを入れられる。これはより浅いツリーと高速な検索につながる

B+tree、ページ、そして InnoDB

  • B+tree の大きな利点の 1 つは、ノードサイズを任意に設定できること
  • InnoDB では B+tree ノードは通常、InnoDB ページサイズである 16k に設定される
  • クエリ処理（したがって B+tree の走査）時、InnoDB はディスクから個別の行や列を読み取らない。データ片にアクセスする必要があるたびに、関連するページ全体をディスクから読み込む
  • InnoDB にはこれを緩和するいくつかの技術があり、主なものは バッファプール である。バッファプールは、ディスク上のページと MySQL クエリ実行の間に位置する、InnoDB ページ向けのメモリ内キャッシュである
  • MySQL がページを読む必要があるとき、まずバッファプール内にすでに存在するか確認する。存在すればそこから読み取り、ディスク I/O を省略する。存在しなければディスク上でページを見つけてバッファプールに追加し、その後クエリ実行を続ける
  • バッファプールはクエリ性能を 劇的に 向上させる。バッファプールがなければ、クエリワークロードを処理するためにはるかに多くのディスク I/O が必要になる

その他のケース

  • ここでは主に順次キーとランダム/UUID キーの比較に焦点を当てたが、これらの原則は、検討中の主キーやセカンダリキーの種類に関係なく覚えておくと役立つ
  • たとえば user.created_at タイムスタンプをインデックスキーとして使うことを検討するかもしれないが、これは順次整数に近い特性を持つ。レガシーデータを挿入しない限り、挿入は通常ほぼ常に最も右側の経路へ進む
  • 一方、user.email_address 文字列のようなものは、ランダムキーにより近い特性を持つ。ユーザーはメールアドレスのアルファベット順にアカウントを作成するわけではないため、挿入は B+tree 全体で発生する

結論

  • B+tree、インデックス、主キー選択について多くを扱った
  • 表面的には簡単に見えても、データベース性能を最大限に引き出すには考慮すべき微妙な違いがある
  • さらに試してみるには、インタラクティブな B+tree ウェブサイト を訪れてみるとよい

関連記事

1件のコメント

 
GN⁺ 2024-09-11
Hacker Newsの意見

  • Wiki を B-Tree のように管理する戦略を使って、有用な状態を保っている

    • ランディングページが多くなりすぎたら、リンクと段落を下位ページへ移す
    • 類似していて古いリンクは、トピックに合った兄弟ページへ移す
    • 最終的に古い文書はランディングページから3段階下へ移動する
    • ドキュメント化は検索の問題に行き着く
    • 金曜の午後を生産的に過ごすのに良いやり方だ

  • 長いことこういうものを探していた、驚くべき投稿だ

    • 複合インデックスに関するセクションがあればよかった

  • 素晴らしい視覚資料に感謝

    • Aerospike 上で BTree+ インデックス対応の作業をした
    • 期限切れのキーを BTree+ から削除するのが難題だった
    • 最初の兄弟リーフノード内でのみ1レベルの分岐を融合することにした
    • BTree+ の上にシャーディングを追加して速度を上げ、ロック競合を減らした
    • クリーンアップの過程で BTree+ が不均衡になることがある
    • インデックス再構築機能を提供して、追加のクリーンアップ作業を避けた

  • Firefox モバイルでクッキーモーダルが動作しない

    • ユーザーがブラウザ側で設定できるようにすべきだ

  • UUID 列を主キーとして使うべきではない

    • 128ビット int をあらゆるリレーション面にコピーしなければならない
    • たいていの場合、完全にランダムだ
    • 内部テーブル間の関係には bigserial（64ビット）の PK を使い、アプリケーションレベルの識別子と自然キーには UUID（128ビット）を使うべきだ
    • データベースはとても快適になるだろう

  • 優れた教材だ

    • このようなインタラクティブなデモは大いに役立つ

  • ディスクブロックと B-Tree ノードが 16k で、キー、値、子ポインタがすべて 8ビットなら、ノードごとに 682 個のキー/値と 683 個の子ポインタを保存できる

    • 3レベルのツリーなら 3億個以上のキー/値ペアを保存できる
    • 各要素は 8バイトであるべきだ

  • 素晴らしい記事だ

    • InnoDB がデータを B ツリー自体に保存することをクラスタ化インデックスと呼ぶ
    • MyISAM は非クラスタ化インデックスだった
    • Oracle などは選べるようにしている

  • グラフの v0、v1、...v10 が何を意味するのかと尋ねている

    • 別のページを意味するのか気になっている

  • 美しいインタラクティブ可視化だ

    • 教育と普及の面で最高水準だ