20220511
數(shù)據(jù)庫(kù)的最簡(jiǎn)單實(shí)現(xiàn)
所有應(yīng)用軟件之中朵纷，數(shù)據(jù)庫(kù)可能是最復(fù)雜的胰坟。
MySQL的手冊(cè)有3000多頁(yè)，PostgreSQL的手冊(cè)有2000多頁(yè)诈闺，Oracle的手冊(cè)更是比它們相加還要厚陪拘。 可以從這個(gè)角度來(lái)說(shuō)Oracle的復(fù)雜程度和掌握上手的難度幾乎等于現(xiàn)在最主流的幾種關(guān)系數(shù)據(jù)庫(kù)的總和厂镇。
但是，自己寫一個(gè)最簡(jiǎn)單的數(shù)據(jù)庫(kù)左刽，做起來(lái)并不難捺信。Reddit上面有一個(gè)帖子，只用了幾百個(gè)字悠反，就把原理講清楚了残黑。下面是這個(gè)帖子整理的內(nèi)容。
一斋否、數(shù)據(jù)以文本形式保存
第一步梨水，就是將所要保存的數(shù)據(jù)，寫入文本文件茵臭。這個(gè)文本文件就是你的數(shù)據(jù)庫(kù)疫诽。
為了方便讀取，數(shù)據(jù)必須分成記錄，每一條記錄的長(zhǎng)度規(guī)定為等長(zhǎng)奇徒。比如雏亚，假定每條記錄的長(zhǎng)度是800字節(jié)，那么第5條記錄的開(kāi)始位置就在3200字節(jié)摩钙。
大多數(shù)時(shí)候罢低，我們不知道某一條記錄在第幾個(gè)位置，只知道主鍵（primary key）的值胖笛。這時(shí)為了讀取數(shù)據(jù)网持，可以一條條比對(duì)記錄。但是這樣做效率太低长踊，實(shí)際應(yīng)用中功舀，數(shù)據(jù)庫(kù)往往采用B樹(shù)（B-tree）格式儲(chǔ)存數(shù)據(jù)。
二身弊、什么是B樹(shù)辟汰？
要理解B樹(shù)，必須從二叉查找樹(shù)（Binary search tree）講起阱佛。
二叉查找樹(shù)是一種查找效率非常高的數(shù)據(jù)結(jié)構(gòu)帖汞，它有三個(gè)特點(diǎn)。
（1）每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子樹(shù)瘫絮。
（2）左子樹(shù)都為小于父節(jié)點(diǎn)的值涨冀，右子樹(shù)都為大于父節(jié)點(diǎn)的值。
（3）在n個(gè)節(jié)點(diǎn)中找到目標(biāo)值麦萤，一般只需要log(n)次比較鹿鳖。
二叉查找樹(shù)的結(jié)構(gòu)不適合數(shù)據(jù)庫(kù)，因?yàn)樗牟檎倚逝c層數(shù)相關(guān)壮莹。越處在下層的數(shù)據(jù)翅帜，就需要越多次比較。極端情況下命满，n個(gè)數(shù)據(jù)需要n次比較才能找到目標(biāo)值涝滴。對(duì)于數(shù)據(jù)庫(kù)來(lái)說(shuō)，每進(jìn)入一層胶台，就要從硬盤讀取一次數(shù)據(jù)歼疮，這非常致命，因?yàn)橛脖P的讀取時(shí)間遠(yuǎn)遠(yuǎn)大于數(shù)據(jù)處理時(shí)間诈唬，數(shù)據(jù)庫(kù)讀取硬盤的次數(shù)越少越好韩脏。
B樹(shù)是對(duì)二叉查找樹(shù)的改進(jìn)。它的設(shè)計(jì)思想是铸磅，將相關(guān)數(shù)據(jù)盡量集中在一起赡矢，以便一次讀取多個(gè)數(shù)據(jù)杭朱，減少硬盤操作次數(shù)。
B樹(shù)的特點(diǎn)也有三個(gè)吹散。
（1）一個(gè)節(jié)點(diǎn)可以容納多個(gè)值弧械。比如上圖中，最多的一個(gè)節(jié)點(diǎn)容納了4個(gè)值空民。
（2）除非數(shù)據(jù)已經(jīng)填滿刃唐，否則不會(huì)增加新的層。也就是說(shuō)袭景，B樹(shù)追求"層"越少越好唁桩。
（3）子節(jié)點(diǎn)中的值，與父節(jié)點(diǎn)中的值耸棒，有嚴(yán)格的大小對(duì)應(yīng)關(guān)系。一般來(lái)說(shuō)报辱，如果父節(jié)點(diǎn)有a個(gè)值与殃，那么就有a+1個(gè)子節(jié)點(diǎn)。比如上圖中碍现，父節(jié)點(diǎn)有兩個(gè)值（7和16）幅疼，就對(duì)應(yīng)三個(gè)子節(jié)點(diǎn)，第一個(gè)子節(jié)點(diǎn)都是小于7的值昼接，最后一個(gè)子節(jié)點(diǎn)都是大于16的值爽篷，中間的子節(jié)點(diǎn)就是7和16之間的值。
這種數(shù)據(jù)結(jié)構(gòu)慢睡，非常有利于減少讀取硬盤的次數(shù)逐工。假定一個(gè)節(jié)點(diǎn)可以容納100個(gè)值，那么3層的B樹(shù)可以容納100萬(wàn)個(gè)數(shù)據(jù)漂辐，如果換成二叉查找樹(shù)泪喊，則需要20層！假定操作系統(tǒng)一次讀取一個(gè)節(jié)點(diǎn)髓涯，并且根節(jié)點(diǎn)保留在內(nèi)存中袒啼，那么B樹(shù)在100萬(wàn)個(gè)數(shù)據(jù)中查找目標(biāo)值，只需要讀取兩次硬盤纬纪。
三蚓再、索引
數(shù)據(jù)庫(kù)以B樹(shù)格式儲(chǔ)存，只解決了按照"主鍵"查找數(shù)據(jù)的問(wèn)題包各。如果想查找其他字段摘仅，就需要建立索引（index）。
所謂索引髓棋，就是以某個(gè)字段為關(guān)鍵字的B樹(shù)文件实檀。假定有一張"雇員表"惶洲，包含了員工號(hào)（主鍵）和姓名兩個(gè)字段∩庞蹋可以對(duì)姓名建立索引文件恬吕，該文件以B樹(shù)格式對(duì)姓名進(jìn)行儲(chǔ)存，每個(gè)姓名后面是其在數(shù)據(jù)庫(kù)中的位置（即第幾條記錄）须床。查找姓名的時(shí)候铐料，先從索引中找到對(duì)應(yīng)第幾條記錄，然后再?gòu)谋砀裰凶x取豺旬。
這種索引查找方法钠惩，叫做"索引順序存取方法"（Indexed Sequential Access Method），縮寫為ISAM族阅。它已經(jīng)有多種實(shí)現(xiàn)（比如C-ISAM庫(kù)和D-ISAM庫(kù)）篓跛，只要使用這些代碼庫(kù)，就能自己寫一個(gè)最簡(jiǎn)單的數(shù)據(jù)庫(kù)坦刀。
四愧沟、高級(jí)功能
部署了最基本的數(shù)據(jù)存取（包括索引）以后鲤遥，還可以實(shí)現(xiàn)一些高級(jí)功能沐寺。
（1）SQL語(yǔ)言是數(shù)據(jù)庫(kù)通用操作語(yǔ)言，所以需要一個(gè)SQL解析器盖奈，將SQL命令解析為對(duì)應(yīng)的ISAM操作混坞。
（2）數(shù)據(jù)庫(kù)連接（join）是指數(shù)據(jù)庫(kù)的兩張表通過(guò)"外鍵"，建立連接關(guān)系钢坦。你需要對(duì)這種操作進(jìn)行優(yōu)化究孕。
（3）數(shù)據(jù)庫(kù)事務(wù)（transaction）是指批量進(jìn)行一系列數(shù)據(jù)庫(kù)操作，只要有一步不成功场钉，整個(gè)操作都不成功蚊俺。所以需要有一個(gè)"操作日志"，以便失敗時(shí)對(duì)操作進(jìn)行回滾逛万。
（4）備份機(jī)制：保存數(shù)據(jù)庫(kù)的副本泳猬。
（5）遠(yuǎn)程操作：使得用戶可以在不同的機(jī)器上，通過(guò)TCP/IP協(xié)議操作數(shù)據(jù)庫(kù)宇植。
