索引的出現(xiàn)其實(shí)就是為了提高數(shù)據(jù)查詢的效率矫户，就像書的目錄一樣。
索引的出現(xiàn)是為了提高查詢效率残邀，但是實(shí)現(xiàn)索引的方式卻有很多種，所以這里也就引入了索引模型的概念柑蛇〗嬲酰可以用于提高讀寫效率的數(shù)據(jù)結(jié)構(gòu)很多，這里簡單介紹一下索引的常見類型

哈希索引

• 是一種以鍵 - 值（key-value）存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)耻台，我們只要輸入待查找的鍵即 key空免，就可以找到其對應(yīng)的值即 Value。哈希的思路很簡單盆耽，把值放在數(shù)組里蹋砚，用一個(gè)哈希函數(shù)把 key 換算成一個(gè)確定的位置，然后把 value 放在數(shù)組的這個(gè)位置
• 不可避免地摄杂，多個(gè) key 值經(jīng)過哈希函數(shù)的換算坝咐，會(huì)出現(xiàn)同一個(gè)值的情況。處理這種情況的一種方法是析恢，拉出一個(gè)鏈表墨坚。
• 哈希索引做區(qū)間查詢的速度是很慢的。

• 哈希表這種結(jié)構(gòu)適用于只有等值查詢的場景映挂，比如 Memcached 及其他一些 NoSQL 引擎泽篮。

  
  
  image.png

有序數(shù)組

• 有序數(shù)組在等值查詢和范圍查詢場景中的性能就都非常優(yōu)秀。
• 等值查詢：用二分法就可以快速得到柑船，這個(gè)時(shí)間復(fù)雜度是 O(log(N))帽撑。
• 范圍查詢，你要查身份證號在[ID_card_X, ID_card_Y]區(qū)間的 User鞍时，可以先用二分法找到 ID_card_X（如果不存在 ID_card_X亏拉，就找到大于 ID_card_X 的第一個(gè) User）历恐，然后向右遍歷，直到查到第一個(gè)大于 ID_card_Y 的身份證號专筷，退出循環(huán)弱贼。
• 僅僅看查詢效率，有序數(shù)組就是最好的數(shù)據(jù)結(jié)構(gòu)了磷蛹。需要更新數(shù)據(jù)的時(shí)候就麻煩了吮旅，你往中間插入一個(gè)記錄就必須得挪動(dòng)后面所有的記錄，成本太高味咳。

• 有序數(shù)組索引只適用于靜態(tài)存儲(chǔ)引擎庇勃。

  
  
  image.png

樹

• 每個(gè)節(jié)點(diǎn)的左兒子小于父節(jié)點(diǎn)，父節(jié)點(diǎn)又小于右兒子槽驶。這樣如果你要查 ID_card_n2 的話责嚷，按照圖中的搜索順序就是按照 UserA -> UserC -> UserF -> User2 這個(gè)路徑得到。這個(gè)時(shí)間復(fù)雜度是 O(log(N))
• 你就需要保持這棵樹是平衡二叉樹掂铐。為了做這個(gè)保證罕拂，更新的時(shí)間復(fù)雜度也是 O(log(N))。
• 樹可以有二叉全陨，也可以有多叉爆班。多叉樹就是每個(gè)節(jié)點(diǎn)有多個(gè)兒子，兒子之間的大小保證從左到右遞增辱姨。二叉樹是搜索效率最高的柿菩，但是實(shí)際上大多數(shù)的數(shù)據(jù)庫存儲(chǔ)卻并不使用二叉樹。其原因是雨涛，索引不止存在內(nèi)存中枢舶，還要寫到磁盤上。
• 為了讓一個(gè)查詢盡量少地讀磁盤替久，就必須讓查詢過程訪問盡量少的數(shù)據(jù)塊凉泄。

• N 叉樹由于在讀寫上的性能優(yōu)點(diǎn)，以及適配磁盤的訪問模式侣肄，已經(jīng)被廣泛應(yīng)用在數(shù)據(jù)庫引擎中了旧困。

  
  
  image.png

B 樹索引和B+ 數(shù)索引

B 樹索引

B樹也稱B-樹,它是一顆多路平衡查找樹。

• 每個(gè)節(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字（可以存有的鍵值對）稼锅。
• 根節(jié)點(diǎn)最少可以只有1個(gè)關(guān)鍵字吼具。
• 非根節(jié)點(diǎn)至少有m/2個(gè)關(guān)鍵字。
• 每個(gè)節(jié)點(diǎn)中的關(guān)鍵字都按照從小到大的順序排列矩距，每個(gè)關(guān)鍵字的左子樹中的所有關(guān)鍵字都小于它拗盒，而右子樹中的所有關(guān)鍵字都大于它。
• 所有葉子節(jié)點(diǎn)都位于同一層锥债，或者說根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的長度都相同陡蝇。
  每個(gè)節(jié)點(diǎn)都存有索引和數(shù)據(jù)痊臭，也就是對應(yīng)的key和value。
• 根節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量范圍：1 <= k <= m-1登夫，非根節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量范圍：m/2 <= k <= m-1广匙。

B樹插入

判斷當(dāng)前結(jié)點(diǎn)key的個(gè)數(shù)是否小于等于m-1，如果滿足恼策，直接插入即可鸦致，如果不滿足，將節(jié)點(diǎn)的中間的key將這個(gè)節(jié)點(diǎn)分為左右兩部分涣楷，中間的節(jié)點(diǎn)放到父節(jié)點(diǎn)中即可

B樹刪除

對于非葉子節(jié)點(diǎn)的刪除分唾，我們需要用后繼key（元素）覆蓋要?jiǎng)h除的key，然后在后繼key所在的子支中刪除該后繼key狮斗。

image.png

image.png

如果刪除葉子節(jié)點(diǎn)绽乔，如果刪除元素后元素個(gè)數(shù)少于（m/2），并且它的兄弟節(jié)點(diǎn)的元素大于（m/2）碳褒，也就是說兄弟節(jié)點(diǎn)的元素比最少值m/2還多折砸，將先將父節(jié)點(diǎn)的元素移到該節(jié)點(diǎn)，然后將兄弟節(jié)點(diǎn)的元素再移動(dòng)到父節(jié)點(diǎn)骤视。

image.png

image.png

image.png

image.png

B+ 樹索引

B+ 樹和B樹是非常相似的

相同點(diǎn)：

• 根節(jié)點(diǎn)至少一個(gè)元素
• 非根節(jié)點(diǎn)元素范圍：m/2 <= k <= m-1

不同點(diǎn)：

• B+樹有兩種類型的節(jié)點(diǎn)：內(nèi)部結(jié)點(diǎn)（也稱索引結(jié)點(diǎn)）和葉子結(jié)點(diǎn)坚弱。內(nèi)部節(jié)點(diǎn)就是非葉子節(jié)點(diǎn)蜀备，內(nèi)部節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，只存儲(chǔ)索引荒叶，數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)碾阁。
• 內(nèi)部結(jié)點(diǎn)中的key都按照從小到大的順序排列腋颠，對于內(nèi)部結(jié)點(diǎn)中的一個(gè)key黍瞧，左樹中的所有key都小于它挣惰，右子樹中的key都大于等于它。葉子結(jié)點(diǎn)中的記錄也按照key的大小排列佛寿。
• 每個(gè)葉子結(jié)點(diǎn)都存有相鄰葉子結(jié)點(diǎn)的指針，葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接多艇。

• 父節(jié)點(diǎn)存有右孩子的第一個(gè)元素的索引

  
  
  image.png

B+樹插入

當(dāng)節(jié)點(diǎn)元素?cái)?shù)量大于m-1的時(shí)候笆环，按中間元素分裂成左右兩部分，中間元素分裂到父節(jié)點(diǎn)當(dāng)做索引存儲(chǔ)嘶居，但是罪帖，本身中間元素還是分裂右邊這一部分的

image.png

image.png

B+樹刪除

葉子節(jié)點(diǎn)有指針的存在，向兄弟節(jié)點(diǎn)借元素時(shí)食听，不需要通過父節(jié)點(diǎn)了胸蛛，而是可以直接通過兄弟節(jié)移動(dòng)即可（前提是兄弟節(jié)點(diǎn)的元素大于m/2），然后更新父節(jié)點(diǎn)的索引樱报；如果兄弟節(jié)點(diǎn)的元素不大于m/2（兄弟節(jié)點(diǎn)也沒有多余的元素）葬项，則將當(dāng)前節(jié)點(diǎn)和兄弟節(jié)點(diǎn)合并，并且刪除父節(jié)點(diǎn)中的key

為什么 MySQL Innodb使用 B+ 樹索引

• Mysql 是一種關(guān)系型數(shù)據(jù)庫迹蛤，區(qū)間訪問是常見的一種情況.
• B 樹能夠在非葉節(jié)點(diǎn)中存儲(chǔ)數(shù)據(jù)民珍，但是這也導(dǎo)致在查詢連續(xù)數(shù)據(jù)時(shí)可能會(huì)帶來更多的隨機(jī) I/O，而 B+ 樹的所有葉節(jié)點(diǎn)可以通過指針相互連接盗飒，能夠減少順序遍歷時(shí)產(chǎn)生的額外隨機(jī) I/O嚷量。

為什么 Mongodb Innodb使用 B 樹索引

• MongoDB 是文檔型的數(shù)據(jù)庫，是一種 nosql逆趣，它使用類 Json 格式保存數(shù)據(jù)蝶溶，數(shù)據(jù)模型簡單。
• B+樹內(nèi)節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)宣渗，所有 data 存儲(chǔ)在葉節(jié)點(diǎn)導(dǎo)致查詢時(shí)間復(fù)雜度固定為 log n抖所。而B 樹查詢時(shí)間復(fù)雜度不固定，與 key 在樹中的位置有關(guān)痕囱，最好為O(1)田轧。