データベースの最も単純な実装

すべてのアプリケーション ソフトウェアの中で、データベースが最も複雑かもしれません。

MySQLのマニュアルは3,000ページ以上、PostgreSQLのマニュアルは2,000ページ以上、Oracleのマニュアルは両方を合わせたよりも厚いです。

しかし、最も単純なデータベースを自分で書くことは難しくありません。 Reddit には、原理をわずか数百語で明確に説明した投稿があります。以下はこの投稿をもとに私がまとめたものです。

1.データをテキスト形式で保存します

最初のステップは、保存したいデータをテキストファイルに書き込むことです。このテキスト ファイルがデータベースになります。

読みやすくするために、データをレコードに分割し、各レコードの長さが等しくなるように指定する必要があります。たとえば、各レコードの長さが 800 バイトであると仮定すると、5 番目のレコードの開始位置は 3200 バイトになります。

ほとんどの場合、私たちは特定のレコードの位置を知りません。知っているのは主キーの値だけです。このとき、データを読み取るために、レコードを 1 つずつ比較することができます。ただし、実際のアプリケーションでは、データベースはデータの保存に B ツリー形式を使用することがよくあります。

2. B ツリーとは何ですか?

B ツリーを理解するには、二分探索木から始める必要があります。

二分探索木は非常に探索効率の高いデータ構造であり、3つの特徴があります。

(1) 各ノードには最大 2 つのサブツリーがあります。

(2) 左側のサブツリーは親ノードより小さい値を持ち、右側のサブツリーは親ノードより大きい値を持ちます。

(3) n 個のノード間でターゲット値を見つけるには、通常、log(n) の比較のみが必要です。

二分探索木の構造は、探索効率がレベル数に関係するため、データベースには適していません。データが低いほど、より多くの比較が必要になります。極端な場合、ターゲット値を見つけるには、n 個のデータで n 回の比較が必要になります。データベースの場合、レイヤーに入るたびにハードディスクからデータを読み取る必要があります。これは、データベースがデータを読み取る回数が少ないほど、ハードディスクの読み取り時間がはるかに長いためです。ハードディスクであればあるほど良いです。

Bツリーは二分探索木を改良したものです。その設計上の考え方は、複数のデータを一度に読み取ることができ、ハードディスクの操作数を減らすことができるように、関連するデータをできるだけまとめることです。

B-treeにも3つの特徴があります。

(1) ノードは複数の値を保持できます。たとえば、上の図では、最大のノードは 4 つの値を保持します。

(2) データが既に入力されていない限り、新しいレイヤーは追加されません。言い換えれば、B-tree は可能な限り少ない「層」を追求します。

(3) 子ノードの値は、親ノードの値と厳密にサイズが一致します。一般に、親ノードに値がある場合、a+1 個の子ノードが存在します。たとえば、上の図では、親ノードには 2 つの値 (7 と 16) があり、これらは 3 つの子ノードに対応しており、最初の子ノードの値は 7 より小さく、最後の子ノードの値は 16 より大きくなります。 、中央の子ノード 7 ～ 16 の値です。

このデータ構造は、ハードディスクからの読み取り回数を減らすのに非常に役立ちます。ノードが 100 個の値を保持できると仮定すると、3 層の B ツリーは 100 万個のデータを保持できます。これを二分探索ツリーに置き換えると、20 個の層が必要になります。オペレーティング システムが一度に 1 つのノードを読み取り、ルート ノードがメモリ内に残ると仮定すると、B ツリーは 100 万個のデータの中からターゲット値を見つけるためにハードディスクを 2 回読み取るだけで済みます。

3. インデックス

データベースは B ツリー形式で保存されており、「主キー」に従ってデータを検索する問題のみを解決します。他のフィールドを検索したい場合は、インデックスを作成する必要があります。

いわゆるインデックスとは、あるフィールドをキーとしたBツリーファイルのことです。従業員番号 (主キー) と名前の 2 つのフィールドを含む「従業員テーブル」があるとします。名前のインデックス ファイルを作成して、名前を B ツリー形式で保存できます。各名前の後にデータベース内の位置 (つまり、どのレコードが指定されるか) が続きます。名前を検索する場合は、まずインデックスから対応するレコードを見つけてから、テーブルからそれを読み取ります。

このインデックス検索方式を「Indexed Sequential Access Method」、略してISAMといいます。すでに複数の実装 (C-ISAM ライブラリや D-ISAM ライブラリなど) が用意されており、これらのコード ライブラリを使用する限り、最も単純なデータベースを自分で作成できます。

4. 高度な機能

最も基本的なデータ アクセス (インデックス作成を含む) を展開した後、いくつかの高度な機能も実装できます。

(1) SQL 言語はデータベースの汎用操作言語であるため、SQL コマンドを対応する ISAM 操作に解析するには SQL パーサーが必要です。

(2)データベース接続(join)とは、データベース内の2つのテーブル間に「外部キー」を介して接続関係を確立することを指します。この操作を最適化する必要があります。

(3) データベーストランザクション (トランザクション) は、バッチでの一連のデータベース操作を指します。1 つのステップが失敗すると、操作全体が失敗します。そのため、操作が失敗した場合にロールバックできるように「操作ログ」を保持する必要があります。

(4) バックアップの仕組み: データベースのコピーを保存します。

(5) リモート操作: TCP/IP プロトコルを介して、ユーザーが異なるマシン上でデータベースを操作できるようにします。