如何自己實作一個關系型資料庫？
https://www.zhihu.com/question/38870156
作者：robert
連結：https://www.zhihu.com/question/25405073/answer/138210064
來源：知乎
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
Database System Concept 和 Database System Implementation 是兩本不錯的書，但是大家好像隻提到了書，卻沒有說該怎麼做。寫一個資料庫，路徑的選擇很重要，否則很容易放棄。推薦這樣的路徑：
1. 資料庫是一個後端server，是以網絡通信，如何并發處理多個用戶端連接配接，收發資料，是首先要解決的問題。這個問題比較簡單，不再贅述。
2. 資料庫最基本的工作模式，是接收并了解一段代碼，根據這段代碼的邏輯，往伺服器上寫入/讀取一些資料。是以，最基本的子產品有兩個，一個是代碼的解釋和執行， 一個是資料存儲。
a.sql的解釋和執行，可以用lex&yacc簡單寫一個文法解析器，一段sql發過來能夠正确轉換成内部結構體；再圍繞這些内部結構體，寫出語義分析代碼，最終将sql轉換成對存儲子產品的調用。
b.存儲子產品，除了設計好供上層調用的API，重點解決兩個問題：1. 建構B樹，管理一張表的資料； 2.将整顆B樹持久化到磁盤/從磁盤中讀取B樹資料。一般的做法是一個B樹節點對應一個資料塊，一個資料塊對應多條記錄，以及相鄰B樹節點的資料塊位址。 以資料塊為機關寫入，讀取。為優化資料庫的讀寫性能，需要在設計緩存和日志子產品，将資料塊緩存到記憶體，作為讀取操作的緩存；日志則用來優化磁盤資料寫入，将寫入資料塊時的随機寫磁盤，轉換為寫日志的順序寫磁盤，如果當機能夠根據日志恢複資料塊。在保證資料持久化的同時提高磁盤寫入性能。
c.存儲子產品寫好後，還需要一個中繼資料子產品，來描述各資料塊對應的庫表，和資料庫中記錄的語義。簡單的做法，可以把業務表的定義放在配置檔案中，系統啟動後即加載配置檔案，将庫表定義放入記憶體，用來解釋資料塊内容；如果還要支援DDL，即根據SQL語句建立/修改表結構，則可以從create table這條sql的實作入手，去建構中繼資料的管理子產品，一方面做到根據中繼資料解釋資料塊；另一方面做到将中繼資料持久化。
3. 事務支援。事務這套理論，用來解決多使用者并發操作相同庫表時，操作的一緻性問題。理想的情況下，資料庫系統最終需要讓多個并發操作的結果，能夠等同于将這多個操作，進行某種串行排列後執行的結果，即并發操作的可串行化，但是實際上達、做到這一點成本很高，資料庫系能會很差，是以事務理論定義了4種隔離級别，對一緻性做了一些妥協，來保證并發讀寫性能。單機資料庫下，事務機制不管從理論還是實作，都已經非常成熟，但要做好并不容易。
如何設計并實作一個 DBMS？
https://www.zhihu.com/question/25405073
實作簡單的sql增删改查應該可以用python實作的。不過語言隻是工具，原理才是根本，我覺得了解簡單的DB結構還是必要的。
1. 資料庫檔案的組織形式，包括資料檔案和索引檔案。一種是将資料，索引分離存儲（MyISAM），另一種資料庫檔案本身就是按B+樹組織的，也就是資料和索引是同個檔案（InnoDB）。
2. 資料庫檔案的結構：一般按page或block組織，一個block 4k大小。SQLite的資料表就是由一個或多個page構成。
3. 資料庫系統結構：可以參照SQLite的系統結構，将系統分為Front-end前端，和Back-end（後端）。
Front-end：SQL的解析器，将輸入的sql指令進行tokenize，然後對sql文法進行parse，轉化為内部指令格式（後端調用）。
Back-end：要負責catalog的管理，增删改查record時要建立index，也就涉及page/buffer管理。
4. 具體實作：如果不考慮事務，并發，複雜的sql操作，可以參考下面的實作子產品。
作者：陳炳金
連結：https://www.zhihu.com/question/38870156/answer/80538773
來源：知乎
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。