1. 怎麼做資料庫
如下：
2. 如何自己實現一個關系型資料庫
對外數據模型為關系型資料庫，內部的實現主要分成兩大類，一類是disk-based，比如mysql，postgres，一類是memory based，後者包括MemSQL，SAP HAHA，OceanBase。看題目的意思指的是前者。這里說一個disk-based的關系型資料庫涉及多少東西。
上世紀70/80年代內存不大，數據不能都放在內存里，大部分數據都存在磁碟上，讀數據也需要從磁碟讀，然而讀寫磁碟太慢了，所以就在內存里做了一個buffer pool，將已經讀過的數據緩存到buffer pool中，寫的時候也是寫到buffer pool中就返回，buffer pool的功能就是管理數據在磁碟和內存的移動。在buffer pool中數據的管理單位是page。page大小一般幾十KB。一般都可以配置。如果buffer pool中沒有空閑的page，就需要將某一個page提出buffer pool，如果它是dirty page，就需要flush到磁碟，這里又需要一個LRU演算法。一個page包含多條記錄，page的格式需要設計用來支持變長欄位。如果這時宕機了，buffer pool中的數據就丟了。這就需要REDO log，將對數據的修改先寫到redo log中，然後寫buffer pool，然後返回給客戶端，隨後，buffer pool中的dirty page會被刷到數據文件中(NO FORCE)。那麼重啟的時候，數據就能從redo log中恢復。REDO log還沒刷完就刷數據到磁碟可以加快寫入速度，缺點就是恢復的時候需要回放UNDO log，回滾一些還沒有提交的事務的修改。寫log又分為邏輯log和物理log，還有物理邏輯log。簡單說邏輯log就是記錄操作，比如將某個值從1改成2.而物理log記錄具體到record的位置，例如某個page的某個record的某個field，原來的值是多少，新值是多少等。邏輯log的問題是並發情況下不太好恢復成一致。物理log對於某些操作比如create table又過於瑣碎，所以一般資料庫都採用混合的方式。為了跟蹤系統中各種操作的順序，這就需要為log分配id，記做LSN(log sequence number)。系統中記錄各種LSN，比如pageLSN, flushedLSN等等。為了加快宕機恢復速度，需要定期寫checkpoint，checkpoint就是一個LSN。
以上ACID里的C和D有關。下面說A和I，即原子性和隔離性。
這兩個性質通過concurrency control來保證。隔離級別有很多種，最開始有4種，從低到高read uncommitted, read committed, repeatable read, serializable。serializable就是多個事務並發執行的結果和某種順序執行事務的結果相同。除了serializable，其他都有各種問題。比如repeatable read有幻讀問題(phantom)，避免幻讀需要gap lock。read committed有幻讀和不可重復讀問題。後來又多了一些隔離級別，比如snapshot isolation，snapshot isolation也有write skew問題。早期，並發控制協議大多是基於兩階段鎖來做的(2PL)，所以早期只有前面提到的四種隔離級別，後來，又出現一類並發控制協議，統稱為Timestamp Ordering，所以又多了snapshot isolation等隔離級別。關於隔離級別，可以看看這篇論文 http://research.microsoft.com/pubs/69541/tr-95-51.pdf。2PL需要處理deadlock的問題。
Timestamp Ordering大體的思想就是認為事務之間沖突不大，不需要加鎖，只在commit的時候check是否有沖突。屬於一種樂觀鎖。
Timestamp Ordering具體來說包括多種，最常見的MVCC就是這類，還有一類叫做OCC(optimistic concurrency control)。MVCC就是對於事務的每次更新都產生新的版本，使用時間戳做版本號。讀的時候可以讀指定版本或者讀最新的版本。幾乎主流資料庫都支持MVCC，因為MVCC讀寫互相不阻塞，讀性能高。MySQL的回滾段就是用來保存老的版本。MVCC需要有後台線程來做不再需要的版本的回收工作。Postgres的vacuum就是做這事的。OCC和MVCC的區別是，OCC協議中，事務的修改保存在私有空間(比如客戶端)，commit的時候再去檢測沖突，通常的做法是事務開始時看一下自己要修改的數據的最後一次修改的時間戳，提交的時候去check是否這個時間戳變大了，如果是，說明被別人改過了，沖突。沖突後可以回滾或者重試。
上面這些搞定了就實現了資料庫的核心，然後為了性能，需要index，通常有兩種，一種支持順序掃描B+Tree,還有一種是Hash Index。單條讀適合用Hash Index,O(1)時間復雜度，順序掃描只適合用B+Tree，O(logN)復雜度。然後，有些查詢只需要掃描索引就能得到結果，有些查詢直接掃描數據表就能得到結果，有些查詢可以走二級索引，通過二級索引找到數據表然後得到結果。。具體用哪種方式就是優化器的事了。
再外圍一些，關系型資料庫自然需要支持SQL了，由SQL變成最後可以執行的物理執行計劃中間又有很多步，首先SQL通過詞法語法分析生成抽象語法樹，然後planner基於這棵樹生成邏輯執行計劃，邏輯執行計劃的生成通常涉及到等價謂詞重寫，子查詢消除等邏輯層面的優化技術，優化的目的當然是性能。比如等價謂詞重寫，用大於小於謂詞消除like，between .. and..等不能利用索引的謂詞。下一步是邏輯執行計劃生成物理執行計劃，物理執行計劃樹每個節點是一個operator，operator的執行就是實實在在的操作，比如掃表的operator，filter opertor。一個邏輯執行計劃通常可以有多個物理執行對應，選擇哪個就涉及到物理執行計劃優化，這里涉及到經典的cost model，綜合考慮內存,CPU, I/O,網路等。最典型的，三表join，從左到右還是右到左，使用hash join，還是sort merge join等。
3. 具體的資料庫設計與實現過程
大致的講主要是根據用戶的需求，然後設計資料庫的E-R模型，然後將E-R模型圖轉換為各種表，並對其進行資料庫設計範式（範式因不同書籍有不同）的審核，然後進行資料庫的實施，然後運行維護。
一句話來講就是將用戶的需求變成帶有各種關系的表，以及其它的資料庫結構，然後供編程使用
具體如下：
按照規范設計的方法，考慮資料庫及其應用系統開發全過程，將資料庫設計分為以下六個階段
（1）需求分析。
（2）概念設計。
（3）邏輯設計。
（4）物理設計。
（5）資料庫實施。
（6）資料庫運行和維護。
5．1．1 需求分析階段
進行資料庫設計首先必須准確了解與分析用戶需求，包括數據與處理需求。需求分析是整個設計過程的基礎，是最困難、最耗時的一步。作為「地基」的需求分析是否做得充分與准確，決定了在其上構建「資料庫大廈」的速度與質量。需求分析做得不好，可能會導致整個資料庫重新設計，因此，務必引起高度重視。
5．1．2 概念模型設計階段
在概念設計階段，設計人員僅從用戶角度看待數據及其處理要求和約束，產生一個反映用戶觀點的概念模式，也稱為「組織模式」。概念模式能充分反映現實世界中實體間的聯系，又是各種基本數據模型的共同基礎，易於向關系模型轉換。這樣做有以下好處：
（1）資料庫設計各階段的任務相對單一化，設計復雜程度得到降低，便於組織管理。
（2）概念模式不受特定DBMS的限制，也獨立於存儲安排，因而比邏輯設計得到的模式更為穩定。
（3）概念模式不含具體的DBMS所附加的技術細節，更容易為用戶所理解，因而能准確地反映用戶的信息需求。
概念模型設計是整個資料庫設計的關鍵，它通過對用戶需求進行綜合、歸納與抽象，形成一個獨立於具體DBMS的概念模型。如採用基於E-R模型的資料庫設計方法，該階段即將所設計的對象抽象出E-R模型；如採用用戶視圖法，則應設計出不同的用戶視圖。
5．1．3 邏輯模型設計階段
邏輯模型設計階段的任務是將概念模型設計階段得到的基本E-R圖，轉換為與選用的DBMS產品所支持的數據模型相符合的邏輯結構。如採用基於E-R模型的資料庫設計方法，該階段就是將所設計的E-R模型轉換為某個DBMS所支持的數據模型；如採用用戶視圖法，則應進行表的規范化，列出所有的關鍵字以及用數據結構圖描述表集合中的約束與聯系，匯總各用戶視圖的設計結果，將所有的用戶視圖合成一個復雜的資料庫系統。
5．1．4 資料庫物理設計階段
資料庫的物理結構主要指資料庫的存儲記錄格式、存儲記錄安排和存取方法。顯然，資料庫的物理設計完全依賴於給定的硬體環境和資料庫產品。在關系模型系統中，物理設計比較簡單一些，因為文件形式是單記錄類型文件，僅包含索引機制、空間大小、塊的大小等內容。
物理設計可分五步完成，前三步涉及到物理結構設計，後兩步涉及到約束和具體的程序設計：
（1）存儲記錄結構設計：包括記錄的組成、數據項的類型、長度，以及邏輯記錄到存儲記錄的映射。
（2） 確定數據存放位置：可以把經常同時被訪問的數據組合在一起，「記錄聚簇（cluster）」技術能滿足這個要求。
（3）存取方法的設計：存取路徑分為主存取路徑及輔存取路徑，前者用於主鍵檢索，後者用於輔助鍵檢索。
（4）完整性和安全性考慮：設計者應在完整性、安全性、有效性和效率方面進行分析，作出權衡。
（5）程序設計：在邏輯資料庫結構確定後，應用程序設計就應當隨之開始。物理數據獨立性的目的是消除由於物理結構的改變而引起對應用程序的修改。當物理獨立性未得到保證時，可能會引發對程序的修改。
資料庫物理設計是為邏輯數據模型選取一個最適合應用環境的物理結構，包括存儲結構和存取方法。
5．1．5 資料庫實施階段
根據邏輯設計和物理設計的結果，在計算機系統上建立起實際資料庫結構、裝入數據、測試和試運行的過程稱為資料庫的實施階段。實施階段主要有三項工作。
（1）建立實際資料庫結構。對描述邏輯設計和物理設計結果的程序即「源模式」，經DBMS編譯成目標模式並執行後，便建立了實際的資料庫結構。
（2）裝入試驗數據對應用程序進行調試。試驗數據可以是實際數據，也可由手工生成或用隨機數發生器生成。應使測試數據盡可能覆蓋現實世界的各種情況。
（3）裝入實際數據，進入試運行狀態。測量系統的性能指標，是否符合設計目標。如果不符，則返回到前面，修改資料庫的物理模型設計甚至邏輯模型設計。
5．1．6 資料庫運行和維護階段
資料庫系統正式運行，標志著資料庫設計與應用開發工作的結束和維護階段的開始。運行維護階段的主要任務有四項：
（1）維護資料庫的安全性與完整性：檢查系統安全性是否受到侵犯，及時調整授權和密碼，實施系統轉儲與備份，發生故障後及時恢復。
（2）監測並改善資料庫運行性能：對資料庫的存儲空間狀況及響應時間進行分析評價，結合用戶反應確定改進措施。
（3）根據用戶要求對資料庫現有功能進行擴充。
（4）及時改正運行中發現的系統錯誤。