目錄
- B-Tree 和 B+Tree資料結構
- MySQL的B-Tree索引
- 磁盤存取相關
B-Tree 和 B+Tree資料結構
B-Tree:
結構：B-TREE 每個節點都是一個二進制數組: [key, data]，所有節點都可以存儲資料。key為索引key,data為除key之外的資料。結構如下：
B-Tree資料結構
檢索原理：首先從根節點進行二分查找，如果找到則傳回對應節點的data，否則對相應區間的指針指向的節點遞歸進行查找，直到找到節點或未找到節點傳回null指針。
缺點：1.插入删除新的資料記錄會破壞B-Tree的性質，是以在插入删除時，需要對樹進行一個分裂、合并、轉移等操作以保持B-Tree性質。造成IO操作頻繁。2.區間查找可能需要傳回上層節點重複周遊，IO操作繁瑣。
B+Tree: B-Tree的變種
與B-Tree相比，B+Tree有以下不同點：非葉子節點不存儲data，隻存儲索引key；隻有葉子節點才存儲data。結構如下圖：
B+Tree資料結構
Mysql中B+Tree：在經典B+Tree的基礎上進行了優化，增加了順序通路指針。在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序通路指針的B+Tree。這樣就提高了區間通路性能：如果要查詢key為從18到49的所有資料記錄，當找到18後，隻需順着節點和指針順序周遊就可以一次性通路到所有資料節點，極大提到了區間查詢效率(無需傳回上層父節點重複周遊查找減少IO操作)。
葉子結點之間有順序指針
為什麼Mysql選擇B+TREE索引? B+TREE索引有什麼好處?
索引本身也很大，不可能全部存儲在記憶體中，是以索引往往以索引檔案的形式存儲的磁盤上。這樣的話，索引查找過程中就要産生磁盤I/O消耗，相對于記憶體存取，I/O存取的消耗要高幾個數量級，是以索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數，提升索引效率。
MySQL的B-Tree索引（技術上說B+Tree）
在 MySQL 中，主要有四種類型的索引，分别為： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我們主要分析B-Tree 索引。
B-Tree 索引是 MySQL 資料庫中使用最為頻繁的索引類型，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支援 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支援索引，而且隻支援索引單個 AUTO_INCREMENT 列。
不僅僅在 MySQL 中是如此，實際上在其他的很多資料庫管理系統中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因為 B-Tree 索引的存儲結構在資料庫的資料檢索中有非常優異的表現。
一般來說， MySQL 中的 B-Tree 索引的實體檔案大多都是以 Balance Tree 的結構來存儲的，也就是所有實際需要的資料都存放于 Tree 的 Leaf Node(葉子節點) ，而且到任何一個 Leaf Node 的最短路徑的長度都是完全相同的，是以我們大家都稱之為 B-Tree 索引。當然，可能各種資料庫（或 MySQL 的各種存儲引擎）在存放自己的 B-Tree 索引的時候會對存儲結構稍作改造。如 Innodb 存儲引擎的 B-Tree 索引實際使用的存儲結構實際上是 B+Tree，也就是在 B-Tree 資料結構的基礎上做了很小的改造，在每一個Leaf Node 上面出了存放索引鍵的相關資訊之外，還存儲了指向與該 Leaf Node 相鄰的後一個 LeafNode 的指針資訊（增加了順序通路指針），這主要是為了加快檢索多個相鄰 Leaf Node 的效率考慮。
1. MyISAM索引實作
1）主鍵索引：
MyISAM引擎使用B+Tree作為索引結構，葉節點的data域存放的是資料記錄的位址。下圖是MyISAM主鍵索引的原理圖：
myisam主鍵索引
這裡設表一共有三列，假設我們以Col1為主鍵，上圖是一個MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引檔案僅僅儲存資料記錄的位址。
2）輔助索引（Secondary key）
在MyISAM中，主索引和輔助索引（Secondary key）在結構上沒有任何差別，隻是主索引要求key是唯一的，而輔助索引的key可以重複。如果我們在Col2上建立一個輔助索引，則此索引的結構如下圖所示：
myisam輔助索引
同樣也是一顆B+Tree，data域儲存資料記錄的位址。是以，MyISAM中索引檢索的算法為首先按照B+Tree搜尋算法搜尋索引，如果指定的Key存在，則取出其data域的值，然後以data域的值為位址，讀取相應資料記錄。
MyISAM的索引方式也叫做“非聚集”的，之是以這麼稱呼是為了與InnoDB的聚集索引區分。
2. InnoDB索引實作
然InnoDB也使用B+Tree作為索引結構，但具體實作方式卻與MyISAM截然不同.
1）主鍵索引：
MyISAM索引檔案和資料檔案是分離的，索引檔案僅儲存資料記錄的位址。而在InnoDB中，表資料檔案本身就是按B+Tree組織的一個索引結構，這棵樹的葉節點data域儲存了完整的資料記錄。這個索引的key是資料表的主鍵，是以InnoDB表資料檔案本身就是主索引。
InnoDB主鍵索引
上圖是InnoDB主索引（同時也是資料檔案）的示意圖，可以看到葉節點包含了完整的資料記錄。這種索引叫做聚集索引。因為InnoDB的資料檔案本身要按主鍵聚集，是以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統會自動選擇一個可以唯一辨別資料記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隐含字段作為主鍵，這個字段長度為6個位元組，類型為長整形。
2）InnoDB的輔助索引
InnoDB的所有輔助索引都引用主鍵作為data域。例如，下圖為定義在Col3上的一個輔助索引：
InnoDB輔助索引
InnoDB 表是基于聚簇索引建立的。是以InnoDB 的索引能提供一種非常快速的主鍵查找性能。不過，它的輔助索引（Secondary Index， 也就是非主鍵索引）也會包含主鍵列，是以，如果主鍵定義的比較大，其他索引也将很大。如果想在表上定義 、很多索引，則争取盡量把主鍵定義得小一些。InnoDB 不會壓縮索引。
文字元的ASCII碼作為比較準則。聚集索引這種實作方式使得按主鍵的搜尋十分高效，但是輔助索引搜尋需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄。
不同存儲引擎的索引實作方式對于正确使用和優化索引都非常有幫助，例如知道了InnoDB的索引實作後，就很容易明白為什麼不建議使用過長的字段作為主鍵，因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變得過大。再例如，用非單調的字段作為主鍵在InnoDB中不是個好主意，因為InnoDB資料檔案本身是一顆B+Tree，非單調的主鍵會造成在插入新記錄時資料檔案為了維持B+Tree的特性而頻繁的分裂調整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。
3. InnoDB索引和MyISAM索引的差別
一是主索引的差別，InnoDB的資料檔案本身就是索引檔案。而MyISAM的索引和資料是分開的。
二是輔助索引的差別：InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是位址。而MyISAM的輔助索引和主索引沒有多大差別。
磁盤存取相關
索引一般以檔案形式存儲在磁盤上，索引檢索需要磁盤I/O操作。與主存不同，磁盤I/O存在機械運動耗費，是以磁盤I/O的時間消耗是巨大的。
一個磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉動（各個磁盤必須同步轉動）。在磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的内容。磁頭不能轉動，但是可以沿磁盤半徑方向運動（實際是斜切向運動），每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的（不過目前已經有多磁頭獨立技術，可不受此限制）。
磁盤結構
磁道: 每個同心環叫做一個 扇區: 磁盤的最小存儲單元。 當需要從磁盤讀取資料時，系統會将資料邏輯位址傳給磁盤，磁盤的控制電路按照尋址邏輯将邏輯位址翻譯成實體位址，即确定要讀的資料在哪個磁道，哪個扇區。為了讀取這個扇區的資料，需要将磁頭放到這個扇區上方，為了實作這一點，磁頭需要移動對準相應磁道，這個過程叫做尋道，所耗費時間叫做尋道時間，然後磁盤旋轉将目标扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間。
局部性原理與磁盤預讀:
由于存儲媒體的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分之一，是以為了提高效率，要盡量減少磁盤I/O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使隻需要一個位元組，磁盤也會從這個位置開始，順序向後讀取一定長度的資料放入記憶體。預讀可以提高I/O效率。預讀的長度一般為頁（page:計算機管理存儲器的邏輯塊-通常為4k）的整倍數. 主存和磁盤以頁為機關交換資料。當程式要讀取的資料不在主存中時，會觸發一個缺頁異常，此時系統會向磁盤發出讀盤信号，磁盤會找到資料的起始位置并向後連續讀取一頁或幾頁載入記憶體中。(MySQL中每個Page預設16k)