數據庫的基本原則

數據庫的核心原則

原子性與持久性：原子性（Atomicity）確保一個事務中的所有操作要么全部完成，要么完全不執行，不會出現部分完成的情況。持久性（Durability）則保證一旦事務提交成功，即使發生系統故障，數據的變化也是永久性的。為了實現持久性，可以使用fsync來確保操作系統將數據實際寫入到磁盤而不是僅僅保存在緩存中。當數據庫崩潰時，需要有一種機制來進行恢復，確保數據的一致性和完整性。
基于B樹的鍵值存儲：這是一種常用的組織和存儲數據的方式，特別適合于磁盤上的數據結構。B樹是一種平衡樹，允許搜索、順序訪問、插入和刪除在一個對數時間內完成。通過使用自由列表（free list），可以有效地管理磁盤空間，從而提高性能和效率。
關系數據庫建立在鍵值存儲之上：在這個層次上，表和索引被映射到底層的B樹結構。這允許數據庫系統以一種高效的方式管理和查詢數據。此外，這種類型的數據庫通常支持類似SQL的查詢語言，它包含了解析器和解釋器來處理和優化查詢請求。
事務的并發控制：在多用戶環境中，多個事務可能同時嘗試訪問或修改相同的數據。因此，必須有機制來控制并發事務的執行，以防止數據不一致或其他問題。常見的并發控制技術包括鎖定協議（如兩階段鎖）、時間戳排序和樂觀并發控制等。

理解數據庫的核心原則而不是僅僅掌握術語確實是一個更加有效的方法來學習和構建數據庫。以下是一些關鍵的原則，它們構成了數據庫系統的基礎，并且可以幫助你通過實踐來學習如何構建一個簡單的數據庫。

在這里插入圖片描述

通過實踐學習：原則而非術語

數據庫文獻中充滿了令人困惑且含義重疊的術語，閱讀這些內容時很容易迷失方向。另一方面，費曼曾說過：“我不能構建的東西，我就不理解。” 那么，你能通過閱讀有關數據庫的內容來構建一個數據庫嗎？測試一下你的理解吧！

雖然有很多東西需要學習，但并非所有知識都同等重要。構建一個數據庫只需要掌握幾個基本的原則，因此任何人都可以嘗試。

核心原則

數據模型：
- 數據庫需要定義如何組織和存儲數據。最基本的數據模型之一是鍵值對（Key-Value），它簡單直觀，非常適合初學者理解數據庫的基本操作如插入、查找、更新和刪除。
持久性與恢復：
- 數據庫必須能夠將數據持久化到非易失性存儲介質中，例如硬盤。使用寫前日志（Write-Ahead Logging, WAL）是一種常見技術，用于確保即使在系統崩潰的情況下也能恢復數據。
索引結構：
- 為了提高數據檢索效率，數據庫通常會使用索引。B樹或其變體B+樹是常見的索引結構，允許快速查找、插入和刪除操作。
事務處理：
- 事務是指一組操作要么全部執行成功，要么完全不執行，從而保證了數據庫的一致性和完整性。ACID特性（原子性、一致性、隔離性、持久性）是評估事務處理的重要標準。
并發控制：
- 當多個用戶同時訪問數據庫時，必須有一種機制來管理這些訪問，以避免數據不一致的問題。這可以通過鎖機制或者更高級的多版本并發控制（MVCC）實現。

實踐建議

動手實踐：嘗試從頭開始編寫一個簡單的鍵值存儲系統。首先實現基本的PUT和GET功能，并考慮如何持久化這些數據。
逐步擴展：一旦有了基礎的鍵值存儲，可以考慮添加B樹或其他索引來加速查找過程。然后，嘗試實現簡單的事務支持，比如如何確保在一個操作失敗時能夠回滾所有相關更改。
模擬故障：測試你的數據庫在各種異常情況下的表現，例如突然斷電或程序崩潰后能否正確恢復數據。
學習資源：雖然避免過多的專業術語很重要，但了解一些基礎概念還是必要的。可以選擇那些強調實際構建而非單純理論講解的學習材料或教程。

手機使用SQLite而非其他格式（如JSON）存儲數據的原因在于，數據庫系統提供了更高級的數據完整性和可靠性保證，尤其是在處理異常情況時。以下是關于為何選擇SQLite以及如何通過一些技術手段實現數據的持久性和原子性的詳細解釋。

為什么選擇SQLite而不是JSON？

數據完整性和一致性：如果直接使用文件格式（例如JSON），在寫入過程中遭遇崩潰可能會導致數據丟失或損壞。這是因為寫操作可能只完成了一部分，導致文件處于不一致的狀態。
事務支持：SQLite等數據庫管理系統（DBMS）提供事務支持，確保數據要么完全更新成功，要么完全不更新（原子性），同時保證一旦事務提交后數據不會丟失（持久性）。

如何通過技術手段解決這些問題

使用`fsync`實現持久性和原子性

持久性：指的是數據一旦被確認寫入后，即使系統發生故障也不會丟失。在操作系統層面，寫入操作并不總是立即將數據寫入磁盤，而是先存儲在緩存中。為了確保數據確實寫到了磁盤上，可以使用fsync系統調用。它會強制將所有待處理的數據從緩存刷新到磁盤，并等待該過程完成。
原子性：意味著數據更新要么全部完成，要么完全不進行，不存在中間狀態。要實現這一點，一個常見的策略是使用預寫日志（Write-Ahead Logging, WAL）。WAL機制會在實際修改數據之前，首先將這些變更記錄在一個單獨的日志文件中。這樣，即便在數據更新過程中發生了崩潰，也可以通過回放日志來恢復到一致的狀態。
結合使用fsync和WAL：在執行關鍵的寫操作時，不僅需要調用fsync來確保數據已經物理上寫入磁盤，還需要依賴WAL機制來維護數據的原子性。這意味著，在開始任何修改前，先記錄變更；然后使用fsync確保這些記錄已經被安全地保存；最后才應用這些更改，并再次調用fsync以確保所有更改都已妥善保存。

索引數據結構

通過索引控制延遲和成本

數據庫將查詢轉化為結果，而用戶無需了解其內部實現。然而，除了結果本身，延遲和成本（內存、I/O、計算）也是重要的考量因素。這正是分析型（OLAP）和事務型（OLTP）數據庫之間的區別所在。

OLAP：通常涉及大量數據，并執行聚合或連接操作。由于數據量龐大，索引的使用可能有限甚至完全不存在。
OLTP：處理少量數據時依賴索引來快速訪問。目標是低延遲和低成本。

需要注意的是，“事務型”這個詞并不是指數據庫事務，而只是數據庫領域的一個有趣術語。

磁盤數據結構的挑戰

原地更新問題
在磁盤上更新數據時，如果系統崩潰，可能會導致數據處于損壞狀態。磁盤并不是“較慢的RAM”，它的行為與內存完全不同。
隨機訪問 vs. 順序訪問
RAM 中的“R”代表“隨機”（Random），這意味著內存支持高效的隨機訪問。而在磁盤上，即使是固態硬盤（SSD），隨機訪問也比順序訪問慢得多。因此，像二叉樹這樣的數據結構在磁盤上并不適用，而 B 樹和 LSM 樹則更適合。
并發訪問
數據結構的并發訪問也是一個重要話題。多個線程或進程同時訪問數據時，需要確保一致性并避免競爭條件。

為什么 B 樹和 LSM 樹適合磁盤？

B 樹

特點：B 樹是一種平衡樹，專為磁盤設計。它的每個節點可以包含多個鍵值對，從而減少了樹的高度，降低了磁盤 I/O 次數。
優點：
- 支持高效的范圍查詢。
- 節點大小通常與磁盤塊大小一致，優化了順序讀取性能。

LSM 樹（Log-Structured Merge Tree）

特點：LSM 樹通過將寫操作先記錄到內存中的緩沖區（MemTable），然后批量寫入磁盤的方式來優化寫性能。
優點：
- 寫操作通常是順序寫入，性能較高。
- 適合寫密集型工作負載（如日志系統）。
缺點：
- 讀操作可能需要合并多個文件（SSTables），性能稍差。

OLAP 和 OLTP 的索引策略

OLAP：
- 數據量大，查詢復雜，索引的作用有限。
- 常用技術包括列式存儲和分布式計算框架（如 Apache Spark）。
OLTP：
- 數據量小，但要求低延遲。
- 索引是核心，常用結構包括 B 樹、哈希索引等。

基于鍵值對的關聯數據庫

數據庫的兩層接口

SQL幾乎成為了數據庫的代名詞，但它實際上只是數據庫的一個用戶界面，并不是數據庫的核心。真正重要的是其底層的功能實現。另一種更為簡單的接口是鍵值（KV）存儲。通過KV接口，你可以獲取、設置和刪除單個鍵值對，更重要的是，可以以排序順序列出一系列鍵。KV比SQL簡單，因為它處于更低的一層。關系型數據庫就是在類似于KV接口的存儲引擎之上構建的。

查詢語言：解析器與解釋器

盡管代碼行數較多，但創建一個查詢語言的最后一步其實相對簡單——無論是解析器還是解釋器，都可以通過遞歸來實現！這個原則幾乎可以應用到任何計算機語言的設計上，或者在創建自己的編程語言或領域特定語言（DSL）時使用。（有關更多挑戰，請參考我的書《從源代碼到機器碼》）

關系型數據庫如何建立在鍵值對之上

底層存儲：首先，你需要有一個基礎的鍵值存儲系統。這個系統允許你執行基本的操作如GET、SET和DELETE。此外，支持按鍵排序并列出鍵范圍是非常重要的，這為后續的關系模型提供了必要的功能支持。
存儲引擎：在KV存儲的基礎上，構建一個存儲引擎。存儲引擎負責管理數據的實際存儲、索引結構以及事務處理等。對于關系型數據庫來說，這意味著需要將表和索引映射到KV存儲中的鍵值對。
表與索引的映射：
- 表：每張表可以通過一個唯一的鍵前綴來標識，表中的每一行則由不同的鍵表示。例如，鍵可以設計為<table_name>:<primary_key>的形式。
- 索引：為了加速查詢，可以為常用查詢字段建立二級索引。這些索引本身也是KV對，其中鍵通常是索引字段的值，而值是指向原始記錄的引用。
SQL層：在KV存儲和存儲引擎之上，添加SQL層。這包括SQL語句的解析器和解釋器，它們將SQL查詢轉換為底層KV操作。例如，一個簡單的SELECT查詢可能被轉化為一系列的KV查找操作。
遞歸實現解析器和解釋器：雖然聽起來復雜，但是利用遞歸技術，可以有效地構建出SQL查詢的解析器和解釋器。遞歸使得處理嵌套查詢和復雜語法變得更加直觀和易于管理。