システムデザインの概念（part6: Storage：SQL&NoSQL）

### SQL

**SQLデータベースの基礎データ構造はB+木です。**

B木は自己バランス探索木であり、データベースインデックスやファイルシステムなど、効率的な検索、挿入、削除操作をサポートするために広く利用されています。

1. **バランス性**: B木はバランス木であり、木の高さが比較的低くなることを保証し、検索、挿入、削除操作の時間複雑度が対数レベルであることを保証します。

2. **多路探索**: B木のノードは複数の子ノードを持つことができ、各ノードでより多くのキー値ペアを格納できるため、木の高さが減少し、検索効率が向上します。

3. **順序性**: B木では、ノードのキー値が順序に従って格納されるため、範囲クエリなどの操作がより効率的に行えます。

4. **ディスクI/Oの最適化**: B木のノードは通常、ディスクブロックサイズに合わせて設計されており、これによりディスクI/O操作回数が減少し、データアクセス効率が向上します。

B木と比較して、B+木はB木の基礎にいくつかの改善を加えたデータ構造です。

1. **葉ノードにデータを格納**: B+木では、すべてのデータが葉ノードに格納されますが、内部ノードではありません。これにより、B+木の内部ノードはより多くのインデックス項目を格納でき、木の高さが減少し、クエリの効率が向上します。

2. **リーフノードのリンクリスト**: B+木では、すべてのリーフノードがリンクリストで接続されています。これにより、範囲クエリなどの操作がより効率的に行えます。

3. **順次アクセス性能の向上**: リーフノードがリンクリストで接続されているため、B+木は効率的な順次走査操作をサポートし、範囲クエリなどの順次アクセスが適しています。

全体として、B+木は優れたデータ構造であり、データベースインデックスなどのシナリオで広く利用され、効率的な検索、挿入、削除操作を提供し、範囲クエリなどの機能をサポートします。

### ACID

**ACID** はデータベーストランザクションの四つの特性の頭文字をとった略語であり、それぞれが原子性（Atomicity）、一貫性（Consistency）、隔離性（Isolation）、持続性（Durability）を表します。これらの特性はデータベーストランザクションの信頼性、安定性、一貫性を保証します。

以下は各 ACID 特性の簡単な説明です：

1. **原子性（Atomicity）**: 原子性はトランザクションが分割不可能な単位であり、トランザクション内のすべての操作が完全に成功するか、すべて失敗してロールバックすることを保証します。トランザクション内のどれか一つの操作が失敗した場合、全体のトランザクションが元の状態に戻ります。

2. **一貫性（Consistency）**: 一貫性はトランザクションの実行がデータベースの一貫性制約を破壊しないことを保証します。つまり、トランザクションの開始前にデータベースが一貫した状態にあれば、トランザクションの終了後もデータベースは一貫した状態を維持します。つまり、トランザクションの実行結果はデータベースの事前に定義された規則と制約に従う必要があります。

3. **隔離性（Isolation）**: 隔離性は一つのトランザクションの実行が他のトランザクションの実行に影響を与えないことを保証します。つまり、各トランザクションは他のトランザクションの存在を感知せず、自身が唯一の実行トランザクションであるかのように振る舞います。これにより、並行トランザクション間の相互干渉やデータの不整合問題を防止します。一般的に、並行環境での隔離性はロックメカニズムやマルチバージョン並行制御（MVCC）などの技術によって実現されます。

4. **持続性（Durability）**: 持続性は、一度トランザクションが正常にコミットされると、そのトランザクションによって変更されたデータの状態が永続的にデータベースに保存され、失われることがないことを保証します。通常、持続性はトランザクションの操作をログに記録することで実現され、システムがクラッシュまたは故障した場合でも、トランザクションをコミットした状態までデータベースを回復することができます。

これらの ACID 特性はデータベーストランザクションの信頼性と一貫性を保証し、並行環境での効果的なトランザクション管理を可能にします。

### NoSQL: ビッグデータ時代のデータ形態

NoSQLは「Not only sql」の略であり、「not」ではないことを示しています。いくつかのケースでは、伝統的なSQLツールではクエリを実行できないこともあります。主な特徴は、大規模なデータ、高速なワークロード、そして水平スケーリングが可能であることです。いくつかの一般的なNoSQLデータベースとそれらの特徴、および適用シナリオを以下に示します。

1. **キーバリューデータベース**：
   - シンプルなキーバリュー方式でデータを格納します。
   - データはキーと値のペアとして格納され、キーは一意の識別子として機能します。
   - スキーマレスであり、事前に定義されたスキーマは必要ありません。
   - 異なるキーと値は完全に異なる構造を持つことができます。
   - 高速なデータ検索に適しており、Redisはその一例です。

2. **ドキュメントデータベース**：
   - データはドキュメント形式で格納され、JSONに類似しています。
   - 柔軟性を提供し、ドキュメント内のフィールドを独立して追加または削除できます。
   - データの格納形式は、開発者がアプリケーションコードで使用するドキュメントモデルの形式と同じです。
   - MongoDBはよく知られたドキュメントデータベースの例です。

3. **ワイドカラムデータベース**：
   - データを行ではなく列に格納し、大規模なデータセットの効率的な格納と検索が可能です。
   - 高い書き込みスループットが必要であり、特定のデータサブセットの読み取りと集計を最適化する必要があるシナリオに適しています。
   - Apache CassandraやGoogleのBigTableがワイドカラムデータベースの例です。

4. **グラフデータベース**：
   - グラフのような構造でデータを格納し、各ノードがエンティティを参照し、エッジまたは関係で相互に接続されています。
   - 様々な種類の関係、友情、および関連を表現するのに適しています。
   - 複雑な関係と相互接続性のデータシナリオに適しており、ソーシャルネットワークなどがその例です。
   - Facebookはグラフデータベースの適用例です。

同時に、SQLデータベースは規模と分散アーキテクチャの処理に問題があります。なぜなら、データは通常単一のサーバーに格納されており、簡単に複数のノードに分割および分散することができないからです。一方、NoSQLデータベースは分散アーキテクチャを考慮し、データの複数ノードへの格納を可能にします。（外部キー制約の削除により、データの分散と分割が容易になりました。）

### 比較

**ACID vs. BASE**：
   - SQLデータベースは通常、ACID（原子性、一貫性、分離性、耐久性）を使用して厳格な一貫性を確保します。
   - NoSQLデータベースは一般に、BASE（基本的な可用性、ソフトステート、最終的な一貫性）を使用してその特性を説明し、最終的な一貫性に重点を置いています。

**最終的な一貫性について**：
   - 最終的な一貫性は、一定期間内にシステムが不整合な状態になる可能性があるが、最終的には一貫した状態になることを指します。
   - リーダー／フォロワーアーキテクチャは、最終的な一貫性を提供する一つのメカニズムであり、主ノード（リーダー）がデータを更新し、他のノード（フォロワー）が最終的に同期更新されます。

全体的に見て、NoSQLデータベースは厳格な一貫性要件を弱め、分散アーキテクチャをサポートすることで、伝統的なSQLデータベースの制約を解消し、大規模データ処理の柔軟性と拡張性を提供します。

伝統的なトランザクション処理データベースに対して、NoSQLは現代のビッグデータ時代のスタンダードです。