是什么影響了數(shù)據(jù)庫索引選型？
主存存取原理
主存的構(gòu)成
主存儲(chǔ)器（簡稱主存或內(nèi)存）包括存取體、各種邏輯部件及控制電路等。存儲(chǔ)體由許多存儲(chǔ)單元組成，每個(gè)存儲(chǔ)單元又包含若干個(gè)存儲(chǔ)元件，每個(gè)存儲(chǔ)元件能寄存一位二進(jìn)制代碼“0”或“1”。這樣，一個(gè)存儲(chǔ)單元可以存儲(chǔ)一串二進(jìn)制代碼，這串二進(jìn)制代碼稱為存儲(chǔ)字，這串二進(jìn)制代碼的位數(shù)稱為存儲(chǔ)字長，可以是8位、16位或者32位等。
主存與CPU的聯(lián)系
MAR（Memory Address Register）是存儲(chǔ)器地址寄存器，用來存放欲訪問的存儲(chǔ)單元的地址，其位數(shù)對應(yīng)存儲(chǔ)單元的個(gè)數(shù)（若MAR為10位，則有210=1024個(gè)存儲(chǔ)單元，記為1k）。
MDR（Memory Data Register）是存儲(chǔ)器數(shù)據(jù)寄存器，用于存放從存儲(chǔ)體某單元取出的代碼或準(zhǔn)備往某存儲(chǔ)單元存入的代碼，其位數(shù)與存儲(chǔ)字長相等。
現(xiàn)代計(jì)算機(jī)一般將MAR和MDR集成在CPU芯片中。
主存的存取過程
如果把存儲(chǔ)體看做是一棟大樓，那么每個(gè)存儲(chǔ)單元可以看成這棟大樓里的每個(gè)房間，每個(gè)存儲(chǔ)元可以看做房間里的一張床位，床位有人相當(dāng)于“1”，無人相當(dāng)于“0”。每個(gè)房間都需要一個(gè)房間號，便于我們找到房間的位置。同樣，可以賦予每個(gè)存儲(chǔ)單元一個(gè)編號，稱為存儲(chǔ)單元的地址號。
主存的工作方式就是按照存儲(chǔ)單元的地址號來實(shí)現(xiàn)對存儲(chǔ)字各位的存（寫入）、?。ㄗx出）。
現(xiàn)代主存的結(jié)構(gòu)和存取原理比較復(fù)雜，這里拋卻具體差別，抽象出一個(gè)十分簡單的存取模型來說明主存的工作原理。
主存的存取過程如下：
當(dāng)系統(tǒng)需要讀取主存時(shí)，首先由CPU將該字的地址送到MAR,經(jīng)地址總線送至主存，然后發(fā)出讀命令。主存接到讀命令后，根據(jù)地址定位到指定存儲(chǔ)單元，然后將此存儲(chǔ)單元數(shù)據(jù)放到數(shù)據(jù)總線上，供其它部件讀取。
寫主存的過程類似，若要向主存存入一個(gè)信息字時(shí)，首先CPU將該字要存入的主存單元的地址經(jīng)MAR送到地址總線，并將信息字送入MDR，然后向主存發(fā)出寫命令，主存接到寫命令后，便將數(shù)據(jù)總線上的信息寫入到對應(yīng)地址總線指出的主存單元中。
畫外音：實(shí)際上主存存取的過程并沒有這么簡單，還需要經(jīng)過經(jīng)過地址譯碼（邏輯地址—>物理地址）等過程。
磁盤存取原理
我們知道，索引本身也很大，不可能全部存儲(chǔ)在內(nèi)存中（根節(jié)點(diǎn)常駐內(nèi)存），一般以文件形式存儲(chǔ)在磁盤上。那么問題來了，索引檢索需要磁盤I/O操作。與內(nèi)存不同，磁盤I/O存在機(jī)械運(yùn)動(dòng)耗費(fèi)，相對于內(nèi)存存取，I/O存取的消耗要高幾個(gè)數(shù)量級。
磁盤的構(gòu)成
磁盤的整體結(jié)構(gòu)示意圖：
一個(gè)磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉(zhuǎn)動(dòng)（各個(gè)磁盤必須同步轉(zhuǎn)動(dòng)）。在磁盤的一側(cè)有磁頭支架，磁頭支架固定了一組磁頭，每個(gè)磁頭負(fù)責(zé)存取一個(gè)磁盤的內(nèi)容。磁頭不能轉(zhuǎn)動(dòng)，但是可以沿磁盤半徑方向運(yùn)動(dòng)（實(shí)際是斜切向運(yùn)動(dòng)），每個(gè)磁頭同一時(shí)刻也必須是同軸的，即從正上方向下看，所有磁頭任何時(shí)候都是重疊的。
磁盤盤片示意圖：
盤片被劃分成一系列同心環(huán)，圓心是盤片中心，每個(gè)同心環(huán)叫做一個(gè)磁道，所有半徑相同的磁道組成一個(gè)柱面。磁道被沿半徑線劃分成一個(gè)個(gè)小的段，每個(gè)段叫做一個(gè)扇區(qū)，每個(gè)扇區(qū)是磁盤的最小存儲(chǔ)單元。
磁盤的存取過程：
當(dāng)需要從磁盤讀取數(shù)據(jù)時(shí)，系統(tǒng)會(huì)將數(shù)據(jù)邏輯地址傳給磁盤，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數(shù)據(jù)在哪個(gè)磁道，哪個(gè)扇區(qū)。
為了讀取這個(gè)扇區(qū)的數(shù)據(jù)，需要將磁頭放到這個(gè)扇區(qū)上方，為了實(shí)現(xiàn)這一點(diǎn)：
- 首先必須找到柱面，即磁頭需要移動(dòng)對準(zhǔn)相應(yīng)磁道，這個(gè)過程叫做尋道，所耗費(fèi)時(shí)間叫做尋道時(shí)間
- 然后目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下，即磁盤旋轉(zhuǎn)將目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下。這個(gè)過程耗費(fèi)的時(shí)間叫做旋轉(zhuǎn)時(shí)間
所以一次訪盤請求（讀/寫）完成過程由三個(gè)動(dòng)作組成：
- 尋道（時(shí)間）：磁頭移動(dòng)定位到指定磁道
- 旋轉(zhuǎn)延遲（時(shí)間）：等待指定扇區(qū)從磁頭下旋轉(zhuǎn)經(jīng)過
- 數(shù)據(jù)傳輸（時(shí)間）：數(shù)據(jù)在磁盤與內(nèi)存之間的實(shí)際傳輸
局部性原理與磁盤預(yù)讀
由于存儲(chǔ)介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機(jī)械運(yùn)動(dòng)耗費(fèi)，磁盤的存取速度往往是主存的幾百萬分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達(dá)到這個(gè)目的，磁盤往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤也會(huì)從這個(gè)位置開始，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：
局部性原理: CPU訪問存儲(chǔ)器時(shí)，無論是存取指令還是存取數(shù)據(jù)，所訪問的存儲(chǔ)單元都趨于聚集在一個(gè)較小的連續(xù)區(qū)域中。
時(shí)間局部性（Temporal Locality）：如果一個(gè)信息項(xiàng)正在被訪問，那么在近期它很可能還會(huì)被再次訪問。
空間局部性（Spatial Locality）：在最近的將來將用到的信息很可能與現(xiàn)在正在使用的信息在空間地址上是臨近的。
由于磁盤順序讀取的效率很高（不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間），因此對于具有局部性的程序來說，預(yù)讀可以提高I/O效率。
預(yù)讀的長度一般為頁（page）的整倍數(shù)。頁是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊，每個(gè)存儲(chǔ)塊稱為一頁（在許多操作系統(tǒng)中，頁的大小通常為4k），主存和磁盤以頁為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時(shí)，會(huì)觸發(fā)一個(gè)缺頁異常，此時(shí)系統(tǒng)會(huì)向磁盤發(fā)出讀盤信號，磁盤會(huì)找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁或幾頁載入內(nèi)存中，然后異常返回，程序繼續(xù)運(yùn)行。
數(shù)據(jù)庫為什么選用B-/+Tree索引
之前提到過，SQL優(yōu)化的一個(gè)重要原則是減少磁盤I/O次數(shù)，磁盤I/O次數(shù)也是評價(jià)索引結(jié)構(gòu)的優(yōu)劣的指標(biāo)之一。
B-Tree分析：
根據(jù)B-Tree的定義，可知檢索一次最多需要訪問h（B-Tree的高度）個(gè)節(jié)點(diǎn)。數(shù)據(jù)庫系統(tǒng)的設(shè)計(jì)者巧妙利用了磁盤預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。但是邏輯上存儲(chǔ)在一個(gè)頁里并不代表物理上也存儲(chǔ)在一個(gè)頁里，為了達(dá)到這個(gè)目的，每次新建節(jié)點(diǎn)時(shí)，直接申請一個(gè)頁的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁對齊的，就實(shí)現(xiàn)了一個(gè)節(jié)點(diǎn)只需一次I/O。
B-Tree中一次檢索最多需要h-1次I/O，因?yàn)楦?jié)點(diǎn)會(huì)常駐內(nèi)存。復(fù)雜度為O(logdN)。一般實(shí)際應(yīng)用中，出度d是非常大的數(shù)字，通常超過100，因此h非常小（通常不超過3）。所以B-Tree作為索引結(jié)構(gòu)效率是非常高的。這也是為什么數(shù)據(jù)庫不選用紅黑樹作為索引（數(shù)據(jù)結(jié)構(gòu)）的原因，一是因?yàn)榧t黑樹的高度h要大的多；二是紅黑樹節(jié)點(diǎn)在物理上可能是單獨(dú)存儲(chǔ)的，無法利用局部性原理。復(fù)雜度為O(h)，效率明顯比B-Tree差的多。
B+Tree分析：
上B+Tree更適合索引。究其原因，一是因?yàn)锽+Tree內(nèi)節(jié)點(diǎn)去掉了data域，因此可以擁有更大的出度，擁有更好的性能；二是因?yàn)樗腥~子節(jié)點(diǎn)形成有序鏈表，便于范圍查詢；所有的查找最終都會(huì)到葉子節(jié)點(diǎn)，從而保證了查詢性能的穩(wěn)定。
