### 局部性原理 那么為什么數據庫系統普遍使用B+樹作為索引結構，而不選例如紅黑樹其他結構呢？首先要先來介紹下局部性原理和磁盤預讀的概念。 一般來說，索引本身較大，不會全部存儲在內存中，會以**索引文件**的形式存儲在磁盤上。所以索引查找數據過程中就會產生磁盤IO操作，而磁盤IO相對于內存存取非常緩慢，因此索引結構要盡量**減少磁盤IO的存取次數**。 為了減少磁盤IO，磁盤往往會進行數據**預讀**，會從某位置開始，預先向后讀取一定長度的數據放入內存，即**局部性原理**。因為磁盤順序讀取的效率較高，不需要尋道時間，因此可以提高IO效率。 預讀長度一般為頁的整數倍，主存和磁盤以**頁**作為單位交換數據。**當需要讀取的數據不在內存時，觸發缺頁中斷**，系統會向磁盤發出讀取磁盤數據的請求，磁盤找到數據的起始位置并向后連續讀取一頁或幾頁數據載入內存，然后中斷返回，系統繼續運行。而一般數據庫系統設計時會將B+樹節點的大小設置為**一頁**，這樣每個節點的載入只需要一次IO