database - DBMS で使用されるデータ構造

Question

Oracle、MySQL、Sqlite などの DBMS でレコードの保存と取得に使用されるデータ構造は何ですか。

Answer 1

通常、B ツリーの巧妙な実装

上記のリンクされたウィキペディアの記事から：

次数 m (各ノードの子の最大数) の B ツリーは、次のプロパティを満たすツリーです。

1. すべてのノードには最大で m 個の子があります。
2. すべてのノード (ルートとリーフを除く) には、少なくとも m⁄2 の子があります。
3. ルートがリーフ ノードでない場合、ルートには少なくとも 2 つの子があります。
4. すべての葉は同じレベルに表示され、情報を伝えます。
5. k 個の子を持つ非リーフ ノードには、k–1 個のキーが含まれます

その利点は、ほとんどの検索ツリー (標準のバイナリ ツリーなど) と同様に対数時間でデータにアクセスできることですが、平均的なケースではタイミング プロパティが優れています。

Answer 2

MySQLにはプラグ可能なストレージ システムがあります。つまり、エンジンは異なるストレージを使用できます。現在、使用できるものは 5 ～ 6 個あります。また、オープンソースであるため、どのように行われるかを見ることができます。

SQLiteは、独自の B-Tree 実装とジャーナリングを使用します。オープンソース - 見ることができます。

FirebirdとInterbaseは、ストレージ用の複数レコード バージョン管理システムで B-Tree を使用しています。Firebird はオープンソースです。一見の価値あり。

Oracle、MS SQL Server、またはその他の独自のデータベース システムについては、ストレージ情報を秘密にしているため、わかりません。