[[270104]]

一般來(lái)說(shuō)，索引本身也很大，不可能全部存儲(chǔ)在內(nèi)存中，因此索引往往以索引文件的形式存儲(chǔ)的磁盤上。這樣的話，索引查找過(guò)程中就要產(chǎn)生磁盤I/O消耗，相對(duì)于內(nèi)存存取，I/O存取的消耗要高幾個(gè)數(shù)量級(jí)，所以評(píng)價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過(guò)程中磁盤I/O操作次數(shù)的漸進(jìn)復(fù)雜度。換句話說(shuō)，索引的結(jié)構(gòu)組織要盡量減少查找過(guò)程中磁盤I/O的存取次數(shù)。

一個(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í)候都是重疊的(不過(guò)目前已經(jīng)有多磁頭獨(dú)立技術(shù)，可不受此限制)。

磁盤結(jié)構(gòu)

磁盤的操作：

• 尋道：讀寫頭連接到一個(gè)傳動(dòng)臂的一端。通過(guò)沿著半徑軸前后移動(dòng)傳動(dòng)臂，驅(qū)動(dòng)器可以將讀寫頭定位到任何磁道上(盤片不動(dòng)，磁頭動(dòng))
• 旋轉(zhuǎn)：一旦定位到磁道后，盤片轉(zhuǎn)動(dòng)，磁道上的每個(gè)位經(jīng)過(guò)磁頭時(shí)，讀寫磁頭就可以感知到位的值，也可以修改值(磁頭不動(dòng)，盤片動(dòng))

磁盤的存儲(chǔ)概念：

• 扇區(qū)：每個(gè)同心環(huán)叫做一個(gè)扇區(qū)，扇區(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)對(duì)準(zhǔn)相應(yīng)磁道，這個(gè)過(guò)程叫做尋道，所耗費(fèi)時(shí)間叫做尋道時(shí)間;然后磁盤旋轉(zhuǎn)將目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下，這個(gè)過(guò)程耗費(fèi)的時(shí)間叫做旋轉(zhuǎn)時(shí)間。
• 頁(yè)：由于存儲(chǔ)介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機(jī)械運(yùn)動(dòng)耗費(fèi)，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達(dá)到這個(gè)目的，磁盤往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤也會(huì)從這個(gè)位置開始，順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。預(yù)讀可以提高I/O效率。預(yù)讀的長(zhǎng)度一般為頁(yè)(page：計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊-通常為4k)的整倍數(shù). 主存和磁盤以頁(yè)為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時(shí)，會(huì)觸發(fā)一個(gè)缺頁(yè)異常，此時(shí)系統(tǒng)會(huì)向磁盤發(fā)出讀盤信號(hào)，磁盤會(huì)找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁(yè)或幾頁(yè)載入內(nèi)存中。

局部性原理

這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：

當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。

也就是說(shuō)，程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中。由于磁盤順序讀取的效率很高(不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間)，因此對(duì)于具有局部性的程序來(lái)說(shuō)，預(yù)讀可以提高I/O效率。

文件系統(tǒng)及數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者利用了磁盤預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。為了達(dá)到這個(gè)目的，在B+Tree每次新建一個(gè)節(jié)點(diǎn)的同時(shí)，直接申請(qǐng)一個(gè)頁(yè)的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁(yè)對(duì)齊的，就實(shí)現(xiàn)了一個(gè)node只需一次I/O。