おい、ハブル！ 記事の翻訳をご紹介します
「リレーショナルデータベースはどのように機能するのか」.

リレーショナル データベースに関しては、何かが欠けていると思わずにはいられません。 どこでも使用されています。 小さくて便利な SQLite から強力な Teradata まで、さまざまなデータベースが利用可能です。 しかし、データベースがどのように機能するかを説明した記事はわずかしかありません。 「howdoesarelationaldatabasework」を使用して自分自身を検索すると、結果がどれほど少ないかを確認できます。 しかも、これらの記事は短いです。 最新の話題のテクノロジー (BigData、NoSQL、または JavaScript) を探している場合は、それらがどのように機能するかを説明するさらに詳細な記事が見つかります。

リレーショナル データベースは大学の授業、研究論文、書籍以外では説明できないほど古く、退屈すぎますか?

開発者として、私は理解できないものを使用することを嫌います。 データベースが 40 年以上使用されているのであれば、必ず理由があるはずです。 私は何年にもわたって、毎日使用しているこれらの奇妙なブラック ボックスを真に理解するために何百時間も費やしてきました。 リレーショナル データベース とても興味深いです。 便利で再利用可能な概念に基づいています。 データベースを理解することに興味はあるが、この幅広いトピックを深く掘り下げる時間や意欲がなかった場合は、この記事をお楽しみください。

この記事のタイトルは露骨ですが、 この記事の目的はデータベースの使用方法を理解することではありません。。 そのため、 簡単な接続リクエストと基本的なクエリの作成方法はすでに知っているはずです。 残酷; そうしないと、この記事を理解できない可能性があります。 知っておくべきことはこれだけです。残りは私が説明します。

アルゴリズムの時間計算量 (BigO) など、コンピューター サイエンスの基礎から始めます。 この概念を嫌う人もいると思いますが、この概念がなければデータベース内の複雑さを理解することはできません。 これは大きなテーマなので、 に焦点を当てます 私が大切だと思うこと: データベースの処理方法 SQL リクエスト。 ただ紹介します データベースの基本概念記事の最後には、内部で何が起こっているのかがわかるようになります。

これは多くのアルゴリズムとデータ構造を含む長くて技術的な記事であるため、時間をかけて読んでください。 一部の概念は理解するのが難しい場合があります。 それらをスキップしても、一般的なアイデアを理解することができます。

より詳しい方のために、この記事は 3 つの部分に分かれています。

• 低レベルおよび高レベルのデータベース コンポーネントの概要
• クエリ最適化プロセスの概要
• トランザクションとバッファプール管理の概要

基本に立ち返って

数年前 (はるか彼方の銀河系で...)、開発者はコーディングしている操作の数を正確に把握する必要がありました。 彼らは、遅いコンピューターの CPU とメモリを無駄にする余裕がなかったので、アルゴリズムとデータ構造を暗記していました。

このパートでは、データベースを理解するために不可欠なこれらの概念のいくつかを思い出してください。 コンセプトも紹介します データベースインデックス.

O(1) 対 O(n2)

最近では、多くの開発者はアルゴリズムの時間計算量を気にしていません...そしてそれは正しいのです。

しかし、大量のデータ (数千のデータではありません) を扱っている場合、またはミリ秒単位で苦労している場合には、この概念を理解することが重要になります。 そしてご想像のとおり、データベースは両方の状況に対処する必要があります。 要点を理解するために必要以上に時間を費やすことはしません。 これは、後でコストベースの最適化の概念を理解するのに役立ちます (コスト ベース 最適化).

コンセプト

アルゴリズムの時間計算量 特定の量のデータに対してアルゴリズムを実行するのにどれくらい時間がかかるかを確認するために使用されます。。 この複雑さを説明するには、ビッグ O 数学表記法を使用します。この表記法は、特定の入力数に対してアルゴリズムが必要な操作の数を記述する関数とともに使用されます。

たとえば、「このアルゴリズムの複雑さは O(some_function()) です」と言うとき、それは、アルゴリズムが一定量のデータを処理するために some_function(a_certain_amount_of_data) の操作を必要とすることを意味します。

この場合、 重要なのはデータ量ではありません**、 さもないと ** データ量の増加に伴って操作数がどのように増加するか。 時間計算量は正確な操作数を提供しませんが、実行時間を見積もるには良い方法です。

このグラフでは、さまざまな種類のアルゴリズムの時間計算量に対する操作の数と入力データの量を確認できます。 対数スケールを使用して表示しました。 言い換えれば、データ量は 1 億から 1 億に急速に増加します。

• O(1) または定数複雑度は一定のままです (そうでなければ、定数複雑度とは呼ばれません)。
• O(ログ(n)) 数十億のデータがあっても低いまま.
• 最悪の難易度 - O(n2)、演​​算数が急速に増加する.
• 他の XNUMX つの合併症も同様に急速に増加します。

例

データ量が少ない場合、O(1) と O(n2) の差は無視できます。 たとえば、2000 個の要素を処理する必要があるアルゴリズムがあるとします。

• O(1) アルゴリズムでは 1 回の操作が必要です
• O(log(n)) アルゴリズムでは 7 回の操作が必要になります
• O(n) アルゴリズムでは 2 回の操作が必要になります
• O(n*log(n)) アルゴリズムでは 14 回の操作が必要になります
• O(n2) アルゴリズムでは 4 回の操作が必要になります

O(1) と O(n2) の差は大きいように見えます (4 万操作) が、まばたきする時間だけで最大 2 ミリ秒が失われます。 実際、最新のプロセッサーは次のような処理を行うことができます。 毎秒数億回のオペレーション。 多くの IT プロジェクトにおいてパフォーマンスと最適化が問題にならないのはこのためです。

先ほども述べたように、膨大な量のデータを扱う場合には、この概念を理解しておくことが依然として重要です。 今回、アルゴリズムが 1 要素を処理する必要がある場合 (これはデータベースとしてはそれほど多くありません):

• O(1) アルゴリズムでは 1 回の操作が必要です
• O(log(n)) アルゴリズムでは 14 回の操作が必要になります
• O(n) アルゴリズムでは 1 回の操作が必要になります
• O(n*log(n)) アルゴリズムでは 14 回の操作が必要になります
• O(n2) アルゴリズムでは 1 回の操作が必要になります

計算はしていませんが、O(n2) アルゴリズムを使用すると、コーヒーを 0 杯 (XNUMX 杯でも!) 飲む時間があると思います。 データ量にさらにXNUMXを加えると、仮眠をとる時間ができます。

さらに深く進んでみましょう

あなたの情報は、次のよう

• 適切なハッシュ テーブル ルックアップでは、O(1) 内の要素が見つかります。
• バランスのとれたツリーを検索すると、O(log(n)) の結果が得られます。
• 配列を検索すると、結果は O(n) で生成されます。
• 最良の並べ替えアルゴリズムの複雑さは O(n*log(n)) です。
• 不適切な並べ替えアルゴリズムの複雑さは O(n2) です。

注: 次の部分では、これらのアルゴリズムとデータ構造について説明します。

アルゴリズムの時間計算量にはいくつかのタイプがあります。

• 平均的なケースのシナリオ
• 最良のシナリオ
• そして最悪のシナリオ

時間の複雑さは、多くの場合最悪のシナリオです。

私はアルゴリズムの時間計算量についてのみ話しましたが、複雑さは以下にも当てはまります。

• アルゴリズムのメモリ消費量
• ディスク I/O 消費アルゴリズム

もちろん、n2 よりもさらに悪い合併症もあります。たとえば、次のとおりです。

• n4: これはひどいです! 前述のアルゴリズムの中には、このような複雑さを伴うものもあります。
• 3n: これはさらにひどいです ! この記事の途中で説明するアルゴリズムの XNUMX つは、この複雑さを持っています (実際に多くのデータベースで使用されています)。
• 階乗 n: たとえ少量のデータでも結果は得られません。
• nn: この複雑さに遭遇した場合は、これが本当にあなたの活動分野なのかどうか自問する必要があります...

注: 私はビッグ O の指定の実際の定義を示したわけではなく、単なるアイデアを示しました。 この記事は次の場所で読むことができます ウィキペディア 実際の（漸近的な）定義については。

マージソート

コレクションを並べ替える必要がある場合はどうしますか? 何？ sort() 関数を呼び出します...わかりました、良い答えです...しかし、データベースの場合、この sort() 関数がどのように機能するかを理解する必要があります。

優れた並べ替えアルゴリズムがいくつかあるため、最も重要なものに焦点を当てます。 マージソート。 現時点ではデータの並べ替えがなぜ役立つのか理解できないかもしれませんが、クエリの最適化の部分を理解した後で理解する必要があります。 さらに、マージ ソートを理解すると、後で「マージ ソート」と呼ばれる一般的なデータベース結合操作を理解するのに役立ちます。 マージ join （合併組合）.

マージ

多くの便利なアルゴリズムと同様、マージ ソートはトリックに依存しています。つまり、サイズ N/2 の 2 つのソートされた配列を結合して N 要素のソート配列を作成するのにかかるコストは N 回の操作だけです。 この操作をマージと呼びます。

これが何を意味するのか、簡単な例で見てみましょう。

この図は、ソートされた最終的な 8 要素配列を構築するには、2 つの 4 要素配列を 4 回繰り返すだけで済むことを示しています。 両方の XNUMX 要素配列がすでにソートされているため、次のようになります。

• 1) XNUMX つの配列内の両方の現在の要素を比較します (最初は current = first)
• 2) 次に、最小のものを取得して 8 要素の配列に入れます。
• 3) 配列内の最小の要素を取得した次の要素に移動します。
• いずれかの配列の最後の要素に到達するまで、1,2,3、XNUMX、XNUMX を繰り返します。
• 次に、他の配列の残りの要素を取得して、8 要素の配列に入れます。

これが機能するのは、両方の 4 要素配列がソートされているため、それらの配列を「戻る」必要がないからです。

トリックは理解できたので、マージの疑似コードを次に示します。

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

マージ ソートでは、問題を小さな問題に分割し、小さな問題の結果を検索して元の問題の結果を取得します (注: このタイプのアルゴリズムは分割統治と呼ばれます)。 このアルゴリズムが理解できなくても、心配する必要はありません。 初めて見たときは理解できませんでした。 お役に立てれば、このアルゴリズムは XNUMX 段階のアルゴリズムであると考えられます。

• 分割フェーズ。アレイがより小さなアレイに分割されます。
• 並べ替えフェーズでは、小さな配列が (ユニオンを使用して) 結合されて、より大きな配列が形成されます。

分割フェーズ

分割段階では、アレイは 3 つのステップでユニタリアレイに分割されます。 正式なステップ数は log(N) です (N=8 なので、log(N) = 3)。

これをどうやって知るのですか？

私は天才です！ 一言で言えば、数学です。 各ステップで元の配列のサイズが 2 で除算されるという考え方です。ステップ数は、元の配列を 2 つに分割できる回数です。 これは、対数 (底 XNUMX) の正確な定義です。

選別フェーズ

並べ替えフェーズでは、ユニタリ (単一要素) 配列から開始します。 各ステップで複数のマージ操作を適用すると、合計コストは N = 8 操作になります。

• 最初のステージでは、それぞれ 4 回の操作が必要な 2 つのマージがあります。
• 2 番目のステップでは、それぞれ 4 回の操作が必要な XNUMX つのマージがあります。
• 1 番目のステップでは、8 つの操作が必要な XNUMX つのマージがあります。

log(N) ステップがあるので、 総コストN * log(N) 操作.

マージソートの利点

なぜこのアルゴリズムは非常に強力なのでしょうか?

なぜなら：

• これを変更してメモリ フットプリントを削減し、新しい配列を作成せずに入力配列を直接変更することができます。

注: このタイプのアルゴリズムは in - 場所 (追加メモリなしでソート)。

• 大幅なディスク I/O オーバーヘッドを発生させることなく、ディスク領域と少量のメモリを同時に使用するように変更できます。 このアイデアは、現在処理中の部分のみをメモリにロードすることです。 これは、100 メガバイトのメモリ バッファーのみを使用してマルチギガバイトのテーブルをソートする必要がある場合に重要です。

注: このタイプのアルゴリズムは 外部ソート.

• 複数のプロセス/スレッド/サーバーで実行するように変更できます。

たとえば、分散マージ ソートは重要なコンポーネントの XNUMX つです。 Hadoopの (これはビッグデータの構造です)。

• このアルゴリズムは鉛を金に変えることができます (本当に!)。

この並べ替えアルゴリズムは (すべてではないにしても) ほとんどのデータベースで使用されていますが、これが唯一のデータベースではありません。 もっと詳しく知りたい場合は、これを読むことができます 研究作業では、一般的なデータベース並べ替えアルゴリズムの長所と短所について説明します。

配列、ツリー、ハッシュテーブル

時間計算量と並べ替えの概念を理解したところで、3 つのデータ構造について説明する必要があります。 これは重要です。 最新のデータベースの基礎となっています。 コンセプトも紹介します データベースインデックス.

アレイ

XNUMX 次元配列は最も単純なデータ構造です。 テーブルは配列として考えることができます。 例えば：

この 2 次元配列は、行と列を含むテーブルです。

• 各行はエンティティを表します
• 列には、エンティティを説明するプロパティが格納されます。
• 各列には、特定のタイプのデータ (整数、文字列、日付など) が格納されます。

これはデータの保存や視覚化には便利ですが、特定の値を検索する必要がある場合には適していません。

たとえば、英国で働くすべての男性を検索したい場合は、各行を調べて、その行が英国に属しているかどうかを判断する必要があります。 N回のトランザクションがかかりますどこ N - 行数、これは悪くありませんが、もっと速い方法はありますか? 今度は木に親しんでみましょう。

注: 最新のデータベースのほとんどは、テーブルを効率的に格納するための拡張配列 (ヒープ構成テーブルとインデックス構成テーブル) を提供します。 ただし、列のグループ内で特定の条件を迅速に見つけるという問題は変わりません。

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

二分探索ツリーは特別なプロパティを持つ二分木であり、各ノードのキーは次のとおりである必要があります。

• 左側のサブツリーに格納されているすべてのキーより大きい
• 右側のサブツリーに格納されているすべてのキーよりも少ない

これが何を意味するかを視覚的に見てみましょう

アイデア

このツリーには N = 15 の要素があります。 208 を探しているとしましょう:

• キーが 136 であるルートから開始します。136<208 なので、ノード 136 の右側のサブツリーを調べます。
• 398>208 したがって、ノード 398 の左側のサブツリーを見ています。
• 250>208 したがって、ノード 250 の左側のサブツリーを見ています。
• 200<208 なので、ノード 200 の右側のサブツリーを見ています。しかし、200 には右側のサブツリーがありません。 値が存在しません (存在する場合、それは右側のサブツリー 200 にあるため)。

では、40 人を探しているとしましょう。

• キーが 136 のルートから開始します。136 > 40 なので、ノード 136 の左側のサブツリーを調べます。
• 80 > 40、したがってノード 80 の左側のサブツリーを見ています。
• 40= 40、 ノードが存在します。 ノード内の行 ID (図にはありません) を取得し、テーブル内で指定された行 ID を探します。
• 行 ID がわかれば、データがテーブル内のどこにあるかを正確に知ることができるので、即座にデータを取得できます。

結局、両方の検索を行うと、ツリー内のレベル数が犠牲になります。 マージ ソートに関する部分を注意深く読むと、log(N) レベルがあることがわかります。 それが判明、 コストログの検索(N)、 悪くない！

問題に戻りましょう

しかし、これは非常に抽象的なので、問題に戻りましょう。 単純な整数の代わりに、前の表の誰かの国を表す文字列を想像してください。 テーブルの「国」フィールド (列 3) を含むツリーがあるとします。

• イギリスで働いている人を知りたい場合
• ツリーを見て、イギリスを表すノードを取得します。
• 「UKnode」内で英国の労働者記録の場所がわかります。

配列を直接使用する場合、この検索には N 操作ではなく log(N) 操作がかかります。 あなたが今提示したのは、 データベースインデックス.

キー (フィールド グループ) を比較する関数があれば、任意のフィールド グループ (文字列、数値、2 行、数値と文字列、日付など) のインデックス ツリーを構築できます。 キー間の順序 (データベース内のすべての基本タイプに当てはまります)。

B+ツリーインデックス

このツリーは特定の値を取得する場合にはうまく機能しますが、必要な場合には大きな問題が発生します。 XNUMX つの値の間の複数の要素を取得する。 ツリー内の各ノードを調べて、これら XNUMX つの値の間にあるかどうかを確認する必要があるため (ツリーの順序付けされた走査などで)、これには O(N) のコストがかかります。 さらに、この操作はツリー全体を読み取る必要があるため、ディスク I/O に適していません。 効率的に実行する方法を見つける必要がある 範囲リクエスト。 この問題を解決するために、最新のデータベースでは、B+Tree と呼ばれる以前のツリーの修正バージョンが使用されています。 B+Tree ツリーでは次のようになります。

• 最下位のノード (葉) のみ 店舗情報 (関連テーブル内の行の位置)
• 残りのノードはここにあります ルーティング用 正しいノードに 検索中.

ご覧のとおり、ここにはさらに多くのノードがあります (XNUMX 回)。 実際、追加のノードである「決定ノード」があり、これは正しいノード (関連するテーブル内の行の位置を格納するノード) を見つけるのに役立ちます。 ただし、検索の複雑さは依然として O(log(N)) です (レベルが XNUMX つだけ増えています)。 大きな違いは、 下位レベルのノードは後続ノードに接続されます.

この B+Tree で、40 から 100 までの値を探している場合:

• 前のツリーの場合と同様に、40 (または 40 が存在しない場合は 40 に最も近い値) を探すだけです。
• 次に、直接相続人リンクを使用して 40 人に達するまで 100 人の相続人を集めます。

M 個の後継者が見つかり、ツリーに N 個のノードがあるとします。 特定のノードを見つけるには、前のツリーと同様に log(N) のコストがかかります。 ただし、このノードを取得すると、後続者への参照を持つ M 個の操作で M 後続者を取得することになります。 この検索には M+log(N) のみのコストがかかります 前のツリーの N 操作と比較した操作。 さらに、ツリー全体 (M+log(N) ノードのみ) を読み取る必要がないため、ディスク使用量が少なくなります。 M が小さく (200 行など)、N が大きい (1 行) 場合、大きな違いが生じます。

しかし、ここで新たな問題が発生します（またしても！）。 データベース (したがって関連する B+Tree インデックス) で行を追加または削除すると、次のようになります。

• B+ ツリー内のノード間の順序を維持する必要があります。そうしないと、ソートされていないツリー内のノードを見つけることができなくなります。
• B+Tree のレベルの最小数を維持する必要があります。そうしないと、O(log(N)) の時間計算量が O(N) になります。

言い換えれば、B+Tree は自己秩序化され、バランスが取れている必要があります。 幸いなことに、これはスマートな削除および挿入操作で可能です。 ただし、これにはコストがかかります。B+ ツリーでの挿入と削除には O(log(N)) のコストがかかります。 だからこそ、そう聞いたことがある人もいるでしょう インデックスを多用しすぎるのは得策ではありません。 本当に、 テーブル内の行の高速な挿入/更新/削除が遅くなります。これは、データベースがインデックスごとにコストのかかる O(log(N)) 操作を使用してテーブルのインデックスを更新する必要があるためです。 さらに、インデックスを追加すると、作業負荷が増加します。 トランザクションマネージャー (記事の最後で説明します)。

詳細については、Wikipedia の記事を参照してください。 B+木。 データベースに B+Tree を実装する例が必要な場合は、こちらをご覧ください。 この記事 и この記事 主要な MySQL 開発者によるものです。 どちらも InnoDB (MySQL エンジン) がインデックスを処理する方法に焦点を当てています。

注: 読者は、低レベルの最適化により、B+ ツリーは完全にバランスが取れているはずだと教えてくれました。

ハッシュ表

最後の重要なデータ構造はハッシュ テーブルです。 これは、値をすばやく調べたい場合に非常に便利です。 さらに、ハッシュ テーブルを理解すると、後でハッシュ結合と呼ばれる一般的なデータベース結合操作を理解するのに役立ちます ( ハッシュ結合）。 このデータ構造は、データベースによって内部的なもの (例: ロックテーブル または バッファプール、これらの概念の両方については後で説明します)。

ハッシュ テーブルは、キーに基づいて要素を迅速に検索するデータ構造です。 ハッシュ テーブルを構築するには、以下を定義する必要があります。

• ключ あなたの要素のために
• ハッシュ関数 鍵用。 計算されたキー ハッシュにより、要素 (と呼ばれる) の位置がわかります。 セグメント ).
• キーを比較する関数。 正しいセグメントが見つかったら、この比較を使用してセグメント内で探している要素を見つける必要があります。

簡単な例

わかりやすい例を見てみましょう。

このハッシュ テーブルには 10 個のセグメントがあります。 私は怠け者なので 5 つのセグメントしかイメージしませんでしたが、あなたは賢いので、残りの 5 つは自分でイメージしてもらいましょう。 キーの 10 を法とするハッシュ関数を使用しました。 言い換えれば、セグメントを見つけるために要素のキーの最後の桁のみを保存します。

• 最後の桁が 0 の場合、要素はセグメント 0 に分類されます。
• 最後の桁が 1 の場合、要素はセグメント 1 に分類されます。
• 最後の桁が 2 の場合、要素は領域 2 に分類されます。
• ...

私が使用した比較関数は、XNUMX つの整数間の単純な等価性です。

要素 78 を取得したいとします。

• ハッシュ テーブルは 78 のハッシュ コードを計算します。つまり 8 です。
• ハッシュ テーブルはセグメント 8 を調べ、最初に見つかった要素は 78 です。
• 彼女はアイテム 78 をあなたに返します
• 検索にかかるコストはわずか 2 操作です (XNUMX つはハッシュ値を計算するため、もう XNUMX つはセグメント内の要素を検索するためです)。

ここで、要素 59 を取得したいとします。

• ハッシュ テーブルは 59 のハッシュ コードを計算します。つまり 9 です。
• ハッシュ テーブルはセグメント 9 を検索し、最初に見つかった要素は 99 です。99!=59 であるため、要素 99 は有効な要素ではありません。
• 同じロジックを使用して、9 番目の要素 (79)、29 番目の要素 (XNUMX)、...、最後の要素 (XNUMX) が取得されます。
• 要素が見つかりません。
• 探索には 7 回の操作が必要です.

優れたハッシュ関数

ご覧のとおり、探している価値に応じて、コストは同じではありません。

ここで、キーのハッシュ関数をモジュロ 1 で変更した場合 (つまり、最後の 000 桁を取得した場合)、セグメント 000 には要素がないため、6 回目の検索にかかる操作は 1 回だけです。 本当の課題は、非常に少数の要素を含むバケットを作成する適切なハッシュ関数を見つけることです。.

私の例では、適切なハッシュ関数を見つけるのは簡単です。 ただし、これは単純な例であり、キーが次の場合、適切なハッシュ関数を見つけるのはより困難になります。

• 文字列 (例: 姓)
• 2 行 (例: 姓と名)
• 2 行と日付 (例: 姓、名、生年月日)
• ...

適切なハッシュ関数を使用すると、ハッシュ テーブルの検索コストは O(1) になります。.

配列とハッシュテーブル

なぜ配列を使用しないのでしょうか?

うーん、良い質問ですね。

• ハッシュ テーブルは次のとおりです。 部分的にメモリにロードされる、残りのセグメントはディスク上に残ることができます。
• 配列では、メモリ内の連続した領域を使用する必要があります。 大きなテーブルをロードしている場合 十分な連続スペースを見つけるのは非常に困難です.
• ハッシュ テーブルの場合、必要なキー (国や人の姓など) を選択できます。

詳細については、次の記事をご覧ください。 Javaハッシュマップ、これはハッシュ テーブルの効率的な実装です。 この記事で説明する概念を理解するために Java を理解する必要はありません。

出所： habr.com