[[270104]]

一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產生磁盤I/O消耗，相對于內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。

一個磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉動(各個磁盤必須同步轉動)。在磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的內容。磁頭不能轉動，但是可以沿磁盤半徑方向運動(實際是斜切向運動)，每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的(不過目前已經有多磁頭獨立技術，可不受此限制)。

磁盤結構

磁盤的操作：

• 尋道：讀寫頭連接到一個傳動臂的一端。通過沿著半徑軸前后移動傳動臂，驅動器可以將讀寫頭定位到任何磁道上(盤片不動，磁頭動)
• 旋轉：一旦定位到磁道后，盤片轉動，磁道上的每個位經過磁頭時，讀寫磁頭就可以感知到位的值，也可以修改值(磁頭不動，盤片動)

磁盤的存儲概念：

• 扇區：每個同心環叫做一個扇區，扇區是磁盤的最小存儲單元。當需要從磁盤讀取數據時，系統會將數據邏輯地址傳給磁盤，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數據在哪個磁道，哪個扇區。為了讀取這個扇區的數據，需要將磁頭放到這個扇區上方，為了實現這一點，磁頭需要移動對準相應磁道，這個過程叫做尋道，所耗費時間叫做尋道時間;然后磁盤旋轉將目標扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間。
• 頁：由于存儲介質的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個字節，磁盤也會從這個位置開始，順序向后讀取一定長度的數據放入內存。預讀可以提高I/O效率。預讀的長度一般為頁(page：計算機管理存儲器的邏輯塊-通常為4k)的整倍數. 主存和磁盤以頁為單位交換數據。當程序要讀取的數據不在主存中時，會觸發一個缺頁異常，此時系統會向磁盤發出讀盤信號，磁盤會找到數據的起始位置并向后連續讀取一頁或幾頁載入內存中。

局部性原理

這樣做的理論依據是計算機科學中著名的局部性原理：

當一個數據被用到時，其附近的數據也通常會馬上被使用。

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

文件系統及數據庫系統的設計者利用了磁盤預讀原理，將一個節點的大小設為等于一個頁，這樣每個節點只需要一次I/O就可以完全載入。為了達到這個目的，在B+Tree每次新建一個節點的同時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個node只需一次I/O。