RDBMSを理解する
takapiRDBMSを理解するために「詳説 データベース ―ストレージエンジンと分散データシステムの仕組み」を読んで、分散データベースや分散ストレージエンジンなどに関しての知見をまとめる。
※ 勉強しながらなので、間違った内容を記載してしまうかもしれません。
takapi1.1 DBMSアーキテクチャ
データベース管理システムではクライアント/サーバーシステムが採用されている。
このモデルではデータベースインスタンス(ノード)がサーバーの役割を果たし、アプリケーションがクライアントの役割を果たしている。
クライアントのリクエストは転送サブシステムを介して受信されている。
リクエストはクエリの形式で送信されている。
データベース管理システムのアーキテクチャ
※ クラスタ通信 <-> 実行エンジンの矢印もあるがmermaidだと変になるので割愛している
クライアント(アプリケーション)からサーバー(データベースインスタンス)への通信の流れ
- クライアントからクエリが転送サブシステムに送られる
- 転送サブシステムは受け取ったクエリをクエリプロセッサに渡す
- クエリパーサでクエリの解析、解釈、検証が行われる
- 解析されたクエリはクエリオプティマイザに渡され、渡されたクエリの最も効率的な実行方法を探索する
- クエリオプティマイザで決定された実行計画を実行エンジンで処理を行う
- データベースサーバーが自身でクエリを実行(ローカル実行)する
- ローカル実行の内容がストレージエンジンによって制御される
takapi- 転送
- クラスタ通信: クラスタ通信は、複数のデータベースサーバーが協力して作業する際に重要です。これは、例えば、大規模なウェブサイトでのデータベースクラスタが考えられます。各サーバーは情報を共有し、クラスタ内でデータを同期させることができます。これは、複数の車が協力して同じ目的地に向かう場面に例えることができます。
- クライアント通信: クライアント通信は、データベースへのアクセスを要求するクライアントアプリケーションとデータベースサーバー間の通信を指します。これは、顧客が注文をウェブサイト経由でデータベースに送信するプロセスとして考えることができます。顧客（クライアント）は注文情報を送り、データベースサーバーはその情報を処理して注文を登録します。
- クエリプロセッサ
- クエリパーサ: クエリパーサは、ユーザーからのクエリを理解し、データベースが理解できる形式に変換します。これは、言語の通訳者のようなものです。たとえば、ユーザーが「すべての在庫が10以上の商品を表示」というクエリを送った場合、クエリパーサはデータベースが理解できるSQLクエリに変換します。
- クエリオプティマイザ: クエリオプティマイザは、クエリを実行するために最適な方法を選択します。これは、料理のレシピの最適な手順を考えることに似ています。たとえば、データベースに複数の商品がある場合、クエリオプティマイザは最も効率的な方法を選んで商品を検索します。
- 実行エンジン
- リモート実行: リモート実行は、データベースサーバーがクエリを実行し、結果をクライアントに返すプロセスを指します。これは、レストランで注文をキッチンに送り、キッチンから料理を受け取るプロセスと同様です。注文はリモートで作成され、料理はローカルで提供されます。
- ローカル実行: ローカル実行は、データベースサーバーが自身でクエリを実行し、結果を生成するプロセスです。これは、料理の調理自体を指します。データベースサーバーはリモートで注文を受けて、それを処理し、結果を提供します。
- ストレージエンジン
- トランザクションマネージャー: トランザクションマネージャーは、データベース内でのトランザクションの整合性を確保します。これは銀行口座の送金を考えると分かりやすいでしょう。トランザクションが途中で失敗した場合、トランザクションマネージャーは口座を以前の状態に戻します。
- ロックマネージャー: ロックマネージャーは、複数のユーザーが同時にデータにアクセスする際の競合を管理します。これは、図書館での本の貸し出しと返却を例に考えることができます。同じ本を同時に借りることを防ぐために、ロックマネージャーが管理を行います。
- アクセスメソッド: アクセスメソッドは、データベース内のデータに効率的にアクセスするための手法を提供します。これは、本を探すための図書館カタログのようなものです。アクセスメソッドは、データの位置を特定し、アクセスを効率化します。
- バッファマネージャー: バッファマネージャーは、データベース内のデータをメモリ内にキャッシュし、アクセス速度を向上させます。これは、図書館が一部の本を棚に常駐させ、頻繁に要求される本にアクセスを高速化することに似ています。
- リカバリマネージャー: リカバリマネージャーは、データベースの障害から回復し、データの完全性を保つ役割を果たします。これは、図書館が火災から回復し、本のコレクションを復元するプロセスに例えることができます。
takapiクエリオプティマイザが実行計画を立てるため、同じSQLを発行しても結果が同一になるとは限らない
要因
- データの変化
- 例えば、あるテーブル内のデータがクエリの実行間に変更された場合、結果が異なることがあります。データベースは常に変化しており、新しいデータが挿入されたり、既存のデータが更新されたりします。これは、レストランのメニューが日替わりで変わるようなものです。同じ注文をしたとしても、提供される料理が異なることがあります。
- インデックスと統計情報
- データベースは、データの高速アクセスのためにインデックスを使用します。クエリオプティマイザは、どのインデックスを使用するかを決定する際に統計情報を考慮します。統計情報が古かったり、正確でなかったりすると、クエリの最適な実行計画が選択されない可能性があります。これは、地図アプリで道路情報が最新でない場合、最短経路が異なることに例えることができます。
- 同時実行トランザクション
- 複数のユーザーが同時にデータベースにアクセスする場合、トランザクションの競合が発生する可能性があります。クエリオプティマイザは、実行計画を決定する際に他のトランザクションの状態を考慮する必要があります。したがって、同じクエリを異なるタイミングで実行すると、競合の結果によって結果が異なることがあります。これは、同じ列車の座席を予約しようとするが、同時に他の人も予約しようとする場面に例えることができます。
- データベース設定
- データベースシステムの設定やパラメータは、クエリの実行計画に影響を与えることがあります。設定が異なる場合、同じクエリでも挙動が変わる可能性があります。これは、車のエンジンチューニングに例えることができます。同じ車でも異なる設定で異なる性能が発揮されます。
要するに、データベースは非常に複雑で、多くの要因が結果に影響を与えるため、同じSQLクエリを発行しても、常に同一の結果を期待することは難しいことがあります。
takapi1.2 メモリベースのDBMSとディスクベースのDBMS
データベース管理システム（DBMS）は、データの格納とアクセスにおいてメモリベースとディスクベースの2つの主要なアーキテクチャを採用している。
メモリベースデータベース
- 概要: メモリベースデータベースは、主にメモリ（RAM）を使用してデータを格納し、高速なアクセスと処理を提供します。ディスクにデータを保存するディスクベースデータベースに比べて非常に高速です。
- 例え: メモリベースデータベースは、あたかも料理の材料を調理中にテーブルの上に配置するようなものです。必要な材料（データ）が手元にあり、料理（処理）が非常に速く進みます。一般的なメモリベースデータベースの例には「Redis」があります。Redisは高速なキャッシュやデータのキー/値ストアとして使用されます。
ディスクベースデータベース
- 概要: ディスクベースデータベースは、データをディスク（HDDまたはSSD）に永続的に保存します。ディスクベースデータベースは大容量のデータを格納できますが、データの読み取りと書き込みに時間がかかります。
- 例え: ディスクベースデータベースは、冷蔵庫や冷凍庫のようなものです。食材（データ）を長期保存するために使用され、必要に応じて取り出すのに時間がかかります。一般的なディスクベースデータベースの例には「MySQL」や「PostgreSQL」があります。これらのデータベースは、大規模なデータセットを永続的に保存するために使用されます。
一部のデータベースシステムは、メモリベースとディスクベースのアプローチを組み合わせて使用することもあります。例えば、一時的なデータや高頻度でアクセスされるデータをメモリに格納し、長期間保存するデータをディスクに保存するといった方法もある。
takapiRAMとは？ [脱線]
RAMとは、ランダムアクセスメモリ（Random Access Memory）の略で、スマホやPCにおいて、CPUが直接アクセスして演算を実行するときに使うメインメモリ（主記憶装置）のこと。 CPUが動作する時に一時的にデータを記憶しておく装置で、一般的に「メモリ」という言葉はこのRAMを指すことが多い。
RAMは「作業する机の面積」です。机の面積が大きいと、様々な道具や資料を置くことができ、一度に多くの作業ができます。RAMも同じで、容量が大きくなるほど多くの作業ができるようになります。
RAMはデータを一時的に読み込んだり書き込んだりしますが、パソコンやスマートフォンの電源を切るとデータは失われます。そのためRAMを「揮発性メモリ」と呼びます。
takapi1.3 列指向DBMSと行指向DBMS
データベース管理システム（DBMS）には、列指向（Column-Oriented）と行指向（Row-Oriented）の2つのデータの格納方法が存在します。
列指向DBMS
- 概要: 列指向データベースは、データを列ごとに格納します。つまり、1つの列のデータをまとめて保存し、同じ列のデータを取り出しやすくするアーキテクチャです。これは、データベース内の各列を縦に積み重ねるようなイメージです。
- 例え: 列指向データベースは、複数の本棚があり、各本棚には同じ種類の本（たとえば、小説、雑誌、参考書など）が整然と並んでいる図書館のようなものです。あなたが特定のカテゴリの本を取り出す際に、同じ本棚の本を一度に取り出すことができます。
- 採用しているDB
- Apache Cassandra: Apache Cassandraは、分散データベースであり、列指向データベースの特徴を持っています。大量のデータを高速に書き込み、クエリできることから、特に時間系列データやイベントログのようなアプリケーションに適しています。
- HBase: HBaseは、Apache Hadoopエコシステムの一部で、大規模なデータセットを扱うのに適しており、列指向のデータモデルを使用しています。主に非構造化データの格納に使用されます。
行指向DBMS
- 概要: 行指向データベースは、データを行ごとに格納します。つまり、1つの行のデータをまとめて保存し、同じ行のデータを取り出しやすくするアーキテクチャです。これは、データベース内の各行が横に並ぶイメージです。
- 例え: 行指向データベースは、本棚があり、各本棚には異なる種類の本が混在している図書館のようなものです。あなたが特定の本を取り出す際に、異なる本棚の本を1冊ずつ取り出す必要があります。
- 採用しているDB
- MySQL: MySQLはリレーショナルデータベース管理システム（RDBMS）の一つであり、行指向データベースの代表例です。データは行ごとに格納され、トランザクション処理に適しています。
- PostgreSQL: PostgreSQLもRDBMSであり、行指向データベースです。データの整合性とトランザクション処理が重視されており、多様なアプリケーションで使用されています。
列指向データベースは、データ分析や集計に向いており、同じ種類のデータを高速に処理できる優れた性能を発揮します。一方、行指向データベースは、トランザクション処理（データの読み取りと書き込み）に適しており、データの整合性を維持するために重要です。
takapi1.4 データファイルとインデックスファイル
データファイル
- 概要: データファイルは、実際のデータレコードが格納されているファイルです。これは、テーブル内の行や列に含まれる実際のデータ（テキスト、数値、画像など）を保持します。データファイルはデータベース内の実際の情報を表しています。
- 例え: データファイルは、図書館の本の棚に置かれた実際の本のようです。各本は個別の情報（タイトル、著者、コンテンツなど）を持ち、それらが実際の本です。データファイルは、データベース内の実際のデータを格納する場所です。
インデックスファイル
- 概要: インデックスファイルは、データの高速検索をサポートするためのファイルです。インデックスは、データベース内のデータの特定の列に関連付けられた、高速で効率的な検索パスを提供します。これにより、データの検索が迅速に行えます。
- 例え: インデックスファイルは、図書館のカタログや目次のようです。カタログには本のタイトル、著者、ジャンルなどの情報が含まれ、それに基づいて本を見つけるのが簡単です。インデックスファイルは、データベース内のデータへの高速なアクセス方法を提供します。
データファイルとインデックスファイルはデータベースの中核を構成し、データの格納と検索を効率的に行うために協力して働きます。データファイルには実際のデータが格納され、インデックスファイルはデータの位置やキーワードへの迅速なアクセスを可能にします。
takapiデータファイルの種類
データベース内でデータを格納する際、データファイルは異なる構造で実装できます。主な実装方法として、インデックス構成表（IOT）、ヒープ構成表（ヒープファイル）、およびハッシュ構成表（ハッシュファイル）があります。
インデックス構成表 (IOT)
- 概要: インデックス構成表（Index-Organized Table、IOT）は、データをインデックスのような構造で格納します。IOTは主にプライマリキーに基づいてデータを整理し、効率的な検索を提供します。
- 例え: IOTは、図書館のカタログのようです。カタログには書籍のタイトルとその所在が含まれ、タイトルに基づいて本を検索できます。カタログ自体がデータの格納場所であり、効率的な検索方法を提供します。
ヒープ構成表 (ヒープファイル)
- 概要: ヒープ構成表（Heap-Organized Table、ヒープファイル）は、データをランダムな順序で格納します。データが追加されるたびに新しい行として追加されます。ヒープファイルは通常、データが順不同で追加される場合に使用されます。
- 例え: ヒープファイルは、手紙やメモをランダムに押し込む引き出しのようです。新しい手紙が到着するたびに引き出しに追加され、手紙を探すときには引き出し内を順不同に見なければなりません。
ハッシュ構成表 (ハッシュファイル)
- 概要: ハッシュ構成表（Hash-Organized Table、ハッシュファイル）は、データをハッシュ関数に基づいて格納します。ハッシュファイルは、特定のハッシュキーに関連付けられた場所にデータを配置し、高速なアクセスを提供します。
- 例え: ハッシュファイルは、郵便番号に基づいて手紙を仕分けするようなものです。各郵便番号に対応する仕分け場所に手紙が配置され、手紙を取り出すときには、対応する郵便番号を知っている必要があります。
これらの異なるデータファイル構成は、データベース内のデータの格納方法を制御し、検索やアクセスの効率を向上させるために使用されます。どの構成を選択するかは、データの特性やアクセスパターンに依存します。
takapi疑問
- いろんなデータベースは必ず上記のどれかを採用しているのか？
- MySQLはInnoDB等のストレージエンジンによって構成表が切り替わる？
ChatGPTに質問したら以下のような回答が帰ってきた
- インデックス構成表 (IOT):
Oracle Database: Oracle Databaseは、インデックス構成表（Index-Organized Table、IOT）をサポートしています。IOTは主にOracle DBMS内で使用され、データベース内のデータを効率的に整理して検索を高速化します。- ヒープ構成表 (ヒープファイル):
PostgreSQL: PostgreSQLは、ヒープ構成表（Heap-Organized Table、ヒープファイル）を使用しています。データがランダムに追加される場合、PostgreSQLはヒープファイルを使用してデータを格納します。- ハッシュ構成表 (ハッシュファイル):
IBM Db2: IBM Db2データベースは、ハッシュ構成表（Hash-Organized Table、ハッシュファイル）をサポートしています。ハッシュファイルは、データをハッシュキーに基づいて格納し、高速なデータの取得を可能にします。
MySQLは以下とのこと
MySQLは通常、ヒープ構成表（Heap-Organized Table、ヒープファイル）を採用しています。データがランダムに追加される場合や特にインデックスのない一時的なテーブルなどにおいて、ヒープ構成表が使用されます。
ただし、MySQLにはインデックス構成表（Index-Organized Table、IOT）やハッシュ構成表（Hash-Organized Table、ハッシュファイル）のような特定のデータファイル構成を提供するためのエンジンも存在します。例えば、InnoDBというMySQLのストレージエンジンは、B-treeインデックスを使用した行指向のデータ構造を持ち、IOTに近い機能を提供します。
データファイル構成の選択は、データベースの要件やデータの性質に応じて行われます。MySQLには、異なるストレージエンジンがあり、これらを使ってデータを異なる方法で格納できるため、選択肢が豊富です。
takapiインデックスファイルのクラスタ化インデックス(Clustered Index)と非クラスタ化インデックス(Non-Clustered Index)
クラスタ化インデックス (Clustered Index)
- 概要: クラスタ化インデックスは、データの物理的な順序を変更することなく、テーブルのデータと直接結びついています。クラスタ化インデックスを持つテーブルは、そのインデックスのキーによって実際のデータが並べ替えられます。したがって、クラスタ化インデックスを持つテーブルは、そのクラスタ化キーに基づいて物理的に整理されています。
- 例え: クラスタ化インデックスは、本の図書館のようです。本は分野別に整理されており、あなたが特定の分野の本を探す場合、クラスタ化された棚に行き、その分野に基づいて本を見つけることができます。
非クラスタ化インデックス (Non-Clustered Index)
- 概要: 非クラスタ化インデックスは、データの物理的な順序を変更せずに、テーブルのデータとは独立してインデックスが作成されます。非クラスタ化インデックスは、インデックスのキーに基づいて、テーブルのデータの位置を示すマップのようなものです。
- 例え: 非クラスタ化インデックスは、辞書の索引のようです。辞書は言葉の頭文字順に整理されており、言葉を探すときに索引を見て、該当のページを見つけることができます。
クラスタ化インデックスと非クラスタ化インデックスの主要な違いは、クラスタ化インデックスがデータの物理的な配置に影響を与え、非クラスタ化インデックスはデータの物理的な順序を変更せずにデータに対する補助的なアクセスを提供する点です。データベース設計時にどちらを使用するかは、データへのアクセスパターンやクエリの要求に依存し、適切な選択を行うことが重要です。
takapi二分探索木 (Binary Search Tree、BST)
BSTは、以下の特徴を持つ木の構造
- 根ノード（Root Node）: 木の最上位にあるノードで、そのノードから始まります。
- 左部分木（Left Subtree）: 根ノードより小さい値を持つノードから構成される部分木。
- 左部分木のすべてのノードはルートノードよりも小さい。
- 右部分木（Right Subtree）: 根ノードより大きい値を持つノードから構成される部分木。
- 右部分木のすべてのノードはルートノードよりも大きい。
- 再帰的な性質: 左部分木と右部分木もそれぞれBSTであるという性質を持ちます。
- 検索の計算量はO(log₂n)という対数に従う
- 先行順走査
- 中央順走査
- 後行順走査
O(log₂n)とは
- O (ビッグ・オー) 記号: O（ビッグ・オー）はアルゴリズムの計算量（実行時間やリソースの使用）を表す記号です。特定のアルゴリズムの計算量を「O(f(n))」と表記します。ここで、f(n) は問題の入力サイズ n に対するアルゴリズムの計算量関数を示します。例えば、O(n) は線形時間、O(n²) は二乗時間を示します。
- log₂n: この部分は、底が 2 の対数を表します。対数（logarithm）は、数学的な操作で、ある数を別の数に変換する操作です。対数は、データの増加率を評価し、計算の効率性を示すために使用されます。底が 2 の場合、log₂n は n を何回 2 で割るかを示し、通常はデータの半分ずつ探索する二分探索の計算量を表します。
例: 二分探索を考えてみましょう。あるソートされたリストから特定の要素を探す場合、二分探索はリストを半分に分割して検索します。例えば、100個の要素があるリストを二分探索する場合、最初に50個の要素を調べて、次に残りの50個を調べる必要があります。次に25個、12個、6個、3個、1個というように探索範囲を狭めていきます。これは対数的な増加です。100個の要素を対数（底が2）で表すと log₂100 ≈ 6.64 です。
したがって、二分探索の計算量は O(log₂n) と表現されます。これは、データが増えても、探索に必要なステップ数が対数的に増加することを示し、非常に効率的なアルゴリズムであることを示します。データベースの検索などで、大きなデータセットからアイテムを高速に見つけるために使用されます。
BST計算のScala実装
適当にScalaで書いてみた
// 二分探索木（BST）のノードを表すクラス
case class Node(key: Int, left: Option[Node] = None, right: Option[Node] = None)
// BSTにノードを挿入する関数
def insert(root: Option[Node], key: Int): Option[Node] = root match
case None => Some(Node(key))
case Some(node) if key < node.key => Some(node.copy(left = insert(node.left, key)))
case Some(node) if key > node.key => Some(node.copy(right = insert(node.right, key)))
case _ => root
// BSTを中間順（inorder）に走査して要素を表示する関数
def inorderTraversal(root: Option[Node]): Unit = root match
case Some(node) =>
inorderTraversal(node.left)
print(s"${node.key} ")
inorderTraversal(node.right)
case None =>
val emptyTree: Option[Node] = None
// 数値を順にBSTに挿入
val root = Seq(5, 3, 8, 6, 4, 2, 1, 7).foldLeft(emptyTree)((acc, key) => insert(acc, key))
// Some(Node(5,Some(Node(3,Some(Node(2,Some(Node(1,None,None)),None)),Some(Node(4,None,None)))),Some(Node(8,Some(Node(6,None,Some(Node(7,None,None)))),None))))
// BSTを中間順に走査して要素を表示
inorderTraversal(root)
// 1 2 3 4 5 6 7 8
takapiディスクベースのDBMS [脱線]
データベース管理システムでの使用において、SSDは一般的にHDDよりも好ましい選択肢とされています。なぜなら、データベースアクセスやクエリの実行が高速で信頼性が高く、データの読み取りおよび書き込みが迅速に行えるためです。ただし、SSDは一般的にHDDよりも高価な場合があるため、予算とパフォーマンスのバランスを考慮する必要がある。
ハードディスクドライブ (HDD)
HDDは物理的なディスクプラッタ（ディスクの円盤）と読み書きヘッドで構成されています。データの読み取りや書き込み時にディスクプラッタが回転し、ヘッドがデータにアクセスします。
HDDの性能は回転速度に依存し、一般的に7,200 RPM（1分間に7,200回転）や5,400 RPMのモデルがあります。
ヘッドの移動とディスクの回転による遅いアクセスタイムがあり、データへのアクセスに時間がかかります。
例: HDDは本棚に本を保存するのに似ており、特定の本にアクセスするには本棚からその本を取り出す必要があり、それには時間がかかります。
通常、HDDは複数のプラッタで構成されていて、それぞれのプラッタの両面または片面にデータが記録されます。
表面にわずかな凹凸があると故障の原因となるため、高い精度の平滑性と表面硬度が求められ、高速回転による振動を抑制できる高い剛性および耐衝撃性も必要となります。これらの特性を備えるためにディスクが硬い(ハード)素材で作られているので、「ハードディスク」と呼ばれています。
なるほど
ソリッドステートドライブ (SSD)
SSDはメカニカルパーツを持たず、データをフラッシュメモリチップに格納します。これにより高速なデータアクセスが可能です。
SSDは物理的な動作がないため、アクセスタイムが非常に速く、データベースへのアクセスが素早く行えます。
SSDは耐久性があり、振動に強く、データの読み書きが静音であり、HDDよりも信頼性が高いことがあります。
例え: SSDは電子的な記憶機器のようなもので、特定の情報を瞬時に取得できるような高速なデジタルアーカイブです。
takapiユビキタスBツリー
Bツリーの特徴
- 平衡木: Bツリーは平衡木の一種で、すべての葉ノードが同じレベルにあるため、高度にバランスが取れています。これにより、検索操作の効率が高いです。
- 多分岐木: 各ノードは複数の子ノードを持ち、ノード内のキーは昇順に格納されています。これにより、多数の値を効率的に管理できます。
- 値の検索: 値の検索は、根ノードから始まり、キーの比較を行い、適切な子ノードに進むことで行います。このプロセスを再帰的に繰り返すことで、目標の値が見つかるか、値が存在しないことが確認されます。
- 値の追加: 新しい値を追加する場合、まず検索を行い、挿入位置を見つけます。適切な位置に値を挿入し、必要に応じてノードを分割することがあります。分割はツリーのバランスを保つために行われます。
値の削除: 値を削除する場合、まず検索を行い、対象の値を見つけます。値を削除した後、ツリーが不均衡にならないようにノードを再編成する必要があることがあります。
なぜBツリーはデータベースのインデックスとして採用されるのか
- 効率的な検索: Bツリーは平衡木であるため、検索操作が非常に高速です。データベース内のレコードを素早く見つけるために使用されます。
- 範囲クエリのサポート: Bツリーは範囲クエリ（例: "値がXからYまでの範囲内のデータを取得"）をサポートするのに適しています。
- 挿入と削除の効率: データの挿入と削除操作も効率的に行えるため、データベースの更新処理にも適しています。
- データベースの物理的な配置: Bツリーのデータ構造はディスク上で連続的に配置でき、ディスクアクセスの効率を向上させます。
- 信頼性と耐久性: Bツリーはデータベースの信頼性と耐久性を向上させるのに役立ちます。データベースのクラッシュや障害が発生しても、データが損失しづらい特徴があります。
ノードの分割
ノード内のキーの数がそのノードが保持できる最大キー数（次数に依存）に達した場合、ノードは分割の対象となります。
分割の順番
- 新しいノードの作成: 分割を始める前に、新しいノード（分割後のノード）を作成します。この新しいノードは既存のノードと同じ深さに配置されます。
- キーのコピー: 元のノードから中央に近いキー（中央値）を新しいノードにコピーします。中央値は、分割に使用され、新しいノードのキーとなります。
- 子ノードの再配置: 元のノードの中央値より小さいキーを持つ子ノードは、元のノードに残り、中央値より大きいキーを持つ子ノードは新しいノードに移動します。この再配置は、ノード内のキーの順序を維持します。
- 親ノードへの中央値の挿入: 中央値（新しいノードのキー）を元のノードの親ノードに挿入します。親ノードが容量いっぱいの場合、同様の分割プロセスが再帰的に適用されることがあります。このプロセスはツリーの上方に向かって続きます。
- 分割の再帰: 分割が親ノードに影響を与える場合、再帰的に分割が続行され、ツリー全体のバランスが維持されます。
新しいノードができたとしても、元のノードのキーは中央値を基準に、2つのノードの間で整理され、検索操作が効率的に行えるようになります。分割はツリー内のデータを適切に配置し、高速な検索および挿入を可能にします。
ノードの結合
結合（マージ）はツリー内のデータを適切に整理し、ツリーのバランスを保つために重要です。特に削除操作が頻繁に行われる場合、結合はデータベースのパフォーマンスを向上させ、余分なノードを削減する役割を果たします。
結合が行われる条件
- ノードがキー不足: ノード内のキーの数が最小許容キー数よりも少ない場合、ノードはキー不足状態になります。最小許容キー数は通常、ノードの次数に依存します。
- 兄弟ノードもキー不足: 削除操作が結合を引き起こす場合、兄弟ノードもキー不足状態である必要があります。この場合、ノードの結合ではなく、再分配（キーの一部を移動）が優先されることがあります。
結合の順番
- 右ノードのキーを左ノードにコピー: 通常、結合は左ノードと右ノードの間で行われます。右ノードのキーを左ノードにコピーし、右ノードは削除されるか、非アクティブ化されます。
- 親ノードのキーの調整: 結合により、右ノードが削除または非アクティブ化された場合、親ノードから右ノードへのリンクが削除され、代わりに左ノードへのリンクを維持します。
- 再帰的な結合: 結合が親ノードに影響を与える場合、このプロセスは再帰的に上方のノードに適用され、ツリーの整合性が維持されます。
takapiファイルフォーマット
- バイナリデータの構成
- プリミティブデータ型のシリアライズ方法
- データ型を結合してセルにする方法
- セルからスロット化ページを作成する方法
- これらの構造内をうまくたどる方法
- 文字列、バイトシーケンス、配列などの可変長データ型を処理する方法
- これらの値のサイズを保持する特別なセルを作成する方法
- ページの外部からセルIDによって個々のセルを参照し、レコードを挿入順で格納し、セルのオフセットをソートすることでキーの並び順を維持するスロット化ページのフォーマット
固定長と可変長
エンディアン
エンディアンはCPUによって決まっていて、PowerPCなどはビッグエンディアン、Intel系などはリトルエンディアン。また MIPS や ARM、SHなど、どちらにもなれるプロセッサも存在していて、バイエンディアンと呼ばれているんだ。
ビットマスク
takapiデータベースページ構造
DBMSでは実際のレコードおよびインデックス情報はテーブルファイルとページに格納される。
CREATE文を実行するとそのテーブル用にテーブルファイルが作成され、レコードを追加を行うとページに格納される。
レコード追加する際にページが存在していないもしくは、ページに格納できる容量がいっぱいの場合新しいページが作成される。
テーブルファイルとページのイメージ
テーブルファイルの中にページが格納されるということだったので、テーブルファイルがフォルダでページがファイルというイメージだと思っていたがそうではない。
テーブルファイルは単一のファイル（例えば、InnoDBの.ibdファイル）であり、その中にページが格納されてるらしい。
つまりExcelで例えると、テーブルファイルがExcelのファイルそのもの（例えば、.xlsxファイル）に相当し、ページはその中の個々のシートのようなものと考える方が近いとのこと。
ただしこのイメージは限界があって、Excelのシートはよりユーザーフレンドリーで直観的なデータ表示のために設計されていて、データベースのページが持つデータの物理的な格納とアクセス方法とは同じように比較できないみたい。
あと、データベースのページは固定サイズ（例えばInnoDBでは16KB）を持つが、Excelのシートにはこのような制約を持ないので、Excelとの比較をする場合はここら辺の違いを理解することが重要みたい。
テーブルファイルとページの検索
ページにはテーブルデータとインデックス情報が格納されているらしく、データベースに対して検索を行うイメージとして、まず対象のインデックスが格納されているページをB木のアルゴリズムを使用して検索を行い、インデックスが持つテーブルレコードの場所情報を探し出す。次にその情報を元にテーブルレコードが格納されているページの検索とページ内から対象のデータを探し出すみたい。
インデックスの検索 -> B-Treeアルゴリズムを使用 -> インデックスからテーブルレコードへ -> テーブルレコードの取得
そしてこれがクラスタ化インデックスの場合は、インデックスが格納されているページと同じ場所にテーブルレコードも格納されているからインデックスの情報を元に再度ページを探しに行く必要が内から早い。
あとは、クラスタ化インデックスの場合レコードはインデックスの順番で並んでいるから範囲検索が早い。
非クラスタ化インデックスだと対象のインデックスを見つけたあと、バラバラに散らばっているレコードも頑張って探さないといけないため。
クラスタ化インデックスだとキレに並んでいるから1 ~ 50まで欲しかったら横並びのやつを取ってこれば済む。
一方でクラスタ化インデックスは、データアクセスは効率化的に行えるがデータの挿入や更新、削除においては、インデックスの再構築が必要になる場合があるため、オーバーヘッドを考慮する必要もある。
疑問
データベースがインデックスを使用して検索を行う場合、対象のレコードがインデックス50であるとして、全レコードが1 ~ 300あるする。
レコードは100件ずつ3つのページに分かれているとして、データベースはB木のアルゴリズムを使用してまずインデックスの格納されているページを探し出すと思うが、どうやってページに格納されている範囲を特定するのか？
例えばページが1, 2, 3とある場合にページ1が1 ~ 100のレコードを持っているという情報をどうやって見つけているのかがわからない。
また、ページ内から対象のインデックスを検索する際もB木のアルゴリズムを使用すると思っているが、そのB木の開始位置はどのようにして決まるのか？
もしかして、ページ内にB木を構成したレコードが格納されておりそちらを使用している？
答え？
疑問として、レコードの取得をB木を使ってやっていると思っていたがそうではないらしい。
B木の役割としては、論理的な検索を行い論理的なアクセスパスを提供する。
つまり、実際に物理的に配置されたレコードをB木のアルゴリズムで検索している訳ではなく、論理的な検索を行いその物理的に配置された対象レコードのアクセスパスを提供するみたい。
確かに、ページ内のレコードの物理的な配置は挿入の順序やその他の要因によって異なるので、これをB木のアルゴリズムを使ったとしても毎度物理的に検索してると大量のディスクアクセスが発生してしまうので早い検索ができる訳がない。
じゃあこの論理的な検索を行うためのデータはどこに格納されているのか？
ページ内の検索を行うためのデータつまりページを管理するためのデータなので、ページヘッダに格納されているのか？
違うらしい。
論理的な検索に必要なB木の構造はページヘッダではなく、ページ内のデータ領域に組み込まれているらしい。
ページ構成
MySQL InnoDBのページ構成
| 名前 | 用途 | 説明 |
|---|---|---|
| ページヘッダ (Page Header) | ページ全体に関する情報を提供 | ページヘッダには、ページの種類、ページ番号、その他のページに関連するメタデータが含まれる。例えば、ページのロック情報、トランザクションID、ページ内の空き領域の量などがこれに該当する。 |
| インフィムム (Infimum) とスプリーム (Supremum) | ページ内のデータ順序を維持するために使用 | 特殊なレコードで、インフィムムはページ内で最小の値を、スプリームは最大の値を示します。これにより、ページ内のデータの並び順が保たれる。 |
| ユーザーレコード (User Records) | 実際のデータを格納 | ページ内に保存されるテーブルの行。各レコードには、行データと一緒にレコードヘッダが含まれ、行の状態やロック情報などが格納され流。 |
| フリースペース (Free Space) | 新しいレコードの追加や既存レコードの更新用に予約されてる。 | ページ内の未使用領域です。ページに新しいデータが追加されるとき、このスペースが使用される。 |
| ページディレクトリ (Page Directory) | ページ内のレコードへの高速アクセスを提供 | ページ内のレコードへのポインターの集合で、ページ内の検索を高速化するために使われる。 |
| ページテイル (Page Tail) | ページの終わりを示す | ページの最後に位置し、ページの終端を示す特定のマークかチェックサムが含まれる |
| トランザクションID (Transaction ID) | トランザクションの識別と管理に使用 | 各ページには、そのページを最後に変更したトランザクションのIDが記録される |
| ロールポインター (Roll Pointer) | バージョニングとロールバックのために使用 | レコードに変更が加えられた際の元の状態へのポインタ |
ページディレクトリはページ内のレコードへの高速アクセスを提供すると記載されているので、ここにB木で論理的な検索を行うためのデータが格納されていると思ったが違うらしい。
ページディレクトリはページレベルでの効率的なアクセスをサポートするために存在し、B木はより広範なテーブルレベルまたはデータベースレベルでの検索を最適化する。
ページディレクトリはB木の一部として機能することもあり、ページ内での特定のレコードへのアクセスを高速化する際に役立つ。
つまりページディレクトリはB木での検索時に補佐的な役割をしてくれるだけ。
B木はユーザーレコードの中に格納されているらしい。
データベースの種類によって異なるが、だいたいこんな感じ？