1. 索引是什么
2. 索引的類型
3. BTree索引
? ? ? ?概念
? ? ? ?舉例：以5階數(shù)為列
4. B+Tree索引
? ? ? ?概念
? ? ? ?5階B+Tree插入舉例
? ? ? ?B+樹的優(yōu)點
? ? ? ?可以使用B+樹索引的查詢類型
? ? ? ?B+Tree索引的限制

索引是什么

? ? ? ?索引是存儲引擎用于快速找到記錄的一種數(shù)據(jù)結(jié)構(gòu)。存儲引擎首先在索引中找到對應(yīng)值镶蹋，然后根據(jù)匹配的索引記錄找到對應(yīng)的數(shù)據(jù)行成艘。比如赏半，
? ? ? ?select first_name from actor where actor.id=5;
? ? ? ?mysql先在索引上按值進行查找，然后返回所有包含該值的數(shù)據(jù)行淆两。

索引的類型

? ? ? ?并沒有統(tǒng)一的索引標準断箫，不同存儲引擎的索引的工作方式并不一樣，也不是所有的存儲引擎都支持所有類型的索引秋冰。即使多個存儲引擎支持同一種類型的索引仲义，其底層的實現(xiàn)也不一樣。
? ? ? ?mysql中常用的索引類型包括BTree索引剑勾、B+Tree索引埃撵、哈希索引。在介紹索引的使用和索引的優(yōu)點之前虽另，需要先弄清楚索引抱哈的暂刘。

BTree索引

概念

? ? ? ?B樹是一種自平衡樹數(shù)據(jù)結(jié)構(gòu)，它維護有序數(shù)據(jù)并允許以對數(shù)時間進行搜索捂刺，順序訪問谣拣，插入和刪除。B樹是二叉搜索樹的一般化族展，因為節(jié)點可以有兩個以上的子節(jié)點森缠。與其他自平衡二進制搜索樹不同，B樹非常適合讀取和寫入相對較大的數(shù)據(jù)塊（如光盤）的存儲系統(tǒng)仪缸。它通常用于數(shù)據(jù)庫和文件系統(tǒng)辅鲸。

定義：

B樹是一種平衡的多分樹，通常我們說m階的B樹腹殿，它必須滿足如下條件：

? ? ? ?1. 每個節(jié)點最多只有m個子節(jié)點独悴。

? ? ? ?2. 每個非葉子節(jié)點（除了根）具有至少? m/2?子節(jié)點。

? ? ? ?3. 如果根不是葉節(jié)點锣尉，則根至少有兩個子節(jié)點自沧。

? ? ? ?4. 具有k個子節(jié)點的非葉節(jié)點包含k -1個鍵。

5. 所有葉子都出現(xiàn)在同一水平拇厢，沒有任何信息（高度一致）。

   什么是階访敌？

image.png

? ? ? ?節(jié)點【13,16,19】擁有的子節(jié)點數(shù)目最多，有四個子節(jié)點（粉色節(jié)點）衣盾，所以可以定義上面的圖片為4階B樹爷抓。

什么是根節(jié)點蓝撇？

? ? ? ?節(jié)點【10】即為根節(jié)點渤昌。包含子節(jié)點數(shù)關(guān)系式2<= M <=m走搁，M為子節(jié)點數(shù)量朱盐；包含的元素數(shù)量 1<= K <=m-1,K為元素數(shù)量兵琳。

什么是內(nèi)部節(jié)點?
? ? ? ?節(jié)點【13,16,19】躯肌、節(jié)點【3,6】都為內(nèi)部節(jié)點清女，特征：內(nèi)部節(jié)點是除葉子節(jié)點和根節(jié)點之外的所有節(jié)點嫡丙，擁有父節(jié)點和子節(jié)點曙博。包含子節(jié)點數(shù)關(guān)系式符合（m/2）<= M <=m關(guān)系式父泳，包含元素數(shù)量M-1惠窄；包含的元素數(shù)量 （m/2）-1<= K <=m-1,K為元素數(shù)量杆融。m/2向上取整。

什么是葉子節(jié)點？
? ? ? ?節(jié)點【1,2】徽惋、節(jié)點【11,12】等最后一層都為葉子節(jié)點险绘，葉子節(jié)點對元素的數(shù)量有相同的限制宦棺，但是沒有
子節(jié)點代咸，也沒有指向子節(jié)點的指針呐芥。葉子節(jié)點的元素符合（m/2）-1<= K <=m-1思瘟。

舉例：以5階數(shù)為列

插入操作

? ? ? ?規(guī)則：

• 若該節(jié)點元素個數(shù)小于m-1滨攻，直接插入光绕；

• 若該節(jié)點元素個數(shù)等于m-1奇钞，引起節(jié)點分裂景埃；以該節(jié)點中間元素為分界谷徙，取中間元素（偶數(shù)個數(shù)完慧，中間兩個隨機選惹帷）插入到父節(jié)點中甲捏；

• 重復上面動作司顿，直到所有節(jié)點符合B樹的規(guī)則大溜；最壞的情況一直分裂到根節(jié)點钦奋，生成新的根節(jié)點锨苏，高度增加1伞租；

  關(guān)鍵點：

• 2<=根節(jié)點子節(jié)點個數(shù)<=5

• 3<=內(nèi)節(jié)點子節(jié)點個數(shù)<=5

• 1<=根節(jié)點元素個數(shù)<=4

• 2<=非根節(jié)點元素個數(shù)<=4

插入8

此時根節(jié)點元素個數(shù)為5，不符合 1<=根節(jié)點元素個數(shù)<=4作喘，進行分裂

接著插入元素【5】，【11】贰锁，【17】時豌熄，不需要任何分裂操作

插入元素【13】

節(jié)點元素超出最大數(shù)量，進行分裂芯肤，提取中間元素【13】崖咨，插入到父節(jié)點當中

接著插入元素【6】逊拍，【12】际邻，【20】世曾，【23】時，不需要任何分裂操作

插入【26】時

最右的葉子結(jié)點空間滿了血巍，需要進行分裂操作，中間元素【20】上移到父節(jié)點中

插入【4】時

導致最左邊的葉子結(jié)點被分裂鲫凶，【4】恰好也是中間元素，上移到父節(jié)點中

【16】,【18】,【24】,【25】陸續(xù)插入不需要任何分裂操作

關(guān)鍵昼钻，插入【19】時

分裂

繼續(xù)分裂

此時樹的高度增加1钥星。

刪除操作

? ? ? ?首先查找B樹中需刪除的元素,如果該元素在B樹中存在，則將該元素在其結(jié)點中進行刪除风喇；刪除該元素后魂莫，首先判斷該元素是否有左右孩子結(jié)點耙考，如果有倦始，則上移孩子結(jié)點中的某相近元素(“左孩子最右邊的節(jié)點”或“右孩子最左邊的節(jié)點”)到父節(jié)點中鞋邑，然后是移動之后的情況；如果沒有肮雨，直接刪除怨规。

• 某結(jié)點中元素數(shù)目小于（m/2）-1,(m/2)向上取整椅亚，則需要看其某相鄰兄弟結(jié)點是否豐滿呀舔；

• 如果豐滿（結(jié)點中元素個數(shù)大于(m/2)-1）媚赖，則向父節(jié)點借一個元素來滿足條件惧磺；

• 如果其相鄰兄弟都不豐滿缤底，即其結(jié)點數(shù)目等于(m/2)-1个唧，則該結(jié)點與其相鄰的某一兄弟結(jié)點進行“合并”成一個結(jié)點徙歼；

刪除【8】

刪除【20】

因為非根節(jié)點元素個數(shù)>=2，只有一個元素【17】的節(jié)點不符合規(guī)定酿秸，因此需要將元素【23】上移動允扇。

刪除【18】

向父結(jié)點借一個元素狭园，然后將最豐滿的相鄰兄弟結(jié)點中上移最后或最前一個元素到父節(jié)點中

最后一步刪除【5】

合并后

image.png

再次合并

image.png

總結(jié)，增加導致分裂管闷，刪除導致合并包个。

注意碧囊，BTree索引每個節(jié)點不但保存索引信息，還保存了對應(yīng)的數(shù)據(jù)行信息熄驼，找到一個節(jié)點相當于找到了數(shù)據(jù)表中的一行瓜贾。

B+Tree索引

概念

? ? ? ?B+Tree是BTree的一個變種序臂，最大的區(qū)別是B+Tree內(nèi)部節(jié)點不保存數(shù)據(jù)奥秆，只保存索引信息构订，所有數(shù)據(jù)都保存在葉子節(jié)點悼瘾，具有如下特征：

• 每個元素不保存數(shù)據(jù)亥宿，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點映企。

• 所有的葉子結(jié)點中包含了全部元素的信息堰氓，及指向含這些元素記錄的指針双絮，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接掷邦。

• 所有的中間節(jié)點元素都同時存在于子節(jié)點抚岗，在子節(jié)點元素中是最大（或最邢蚯馈）元素

不但節(jié)點之間含有重復元素挟鸠，而且葉子結(jié)點還用指針連接在一起。

? ? ? ?在上面這課樹中覆享，根節(jié)點元素8是子節(jié)點2，5凤壁，8的最大元素罚斗，也是葉子節(jié)點6，8的最大元素距淫。需要注意的是根節(jié)點的最大元素（這里是15）喻杈，也就等同于整個B+樹的最大元素缴啡。以后無論插入刪除多少元素秒咐，始終保持最大元素在根節(jié)點當中。
? ? ? ?至于葉子節(jié)點雷滋，由于父節(jié)點的元素都出現(xiàn)在子節(jié)點惊豺，因此葉子結(jié)點包含了全部元素的信息尸昧。并且每個葉子節(jié)點都帶有指向下一個節(jié)點的指針，形成了一個有序鏈表幢妄。

對于B+樹，只需記住葉子節(jié)點是個有序列表且包含全部元素數(shù)據(jù)信息即可潮尝，影響到后續(xù)索引的使用勉失。

5階B+Tree插入舉例

空樹插入【5】

一次插入【8】、【10】徒蟆、【15】

插入【16】

? ? ? ?元素個數(shù)超過限制输莺，進行分裂，分裂規(guī)則同BTree丈冬，但是注意埂蕊，分裂的元素保留在原節(jié)點中疏唾，同時葉子節(jié)點通過指針連接蓄氧。

插入【17】、【18】

元素個數(shù)超過限制槐脏，進行分裂喉童，分裂的元素保留在原節(jié)點中。

image.png

B+樹的優(yōu)點

• 單元素查詢

  在單元素查詢的時候顿天，B+樹會自頂向下逐層查找節(jié)點，最終找到匹配的葉子節(jié)點牌废。

  比如我們查找元素4

第一次磁盤IO

第二次磁盤IO

第三次磁盤IO

? ? ? ?B+樹的中間節(jié)點只保存索引信息咽白，不保存元素其他相關(guān)信息晶框，所以同樣大小的磁盤頁可以容納更多的節(jié)點元素授段，這就意味著在數(shù)據(jù)量相同的情況下畴蒲，B+樹更加的矮胖，因此IO的次數(shù)也就較少掩宜。B+樹查詢必須查找到葉子節(jié)點牺汤，每一次查找都是穩(wěn)定的檐迟；

• B樹的范圍查找及過程與B+樹對比

比如，查找范圍3~11

B樹溶其，首先自頂向下,查找到范圍的下限(3)

中序遍歷到元素6

中序遍歷到元素8

中序遍歷到元素9

中序遍歷到元素11

B+樹,自頂向下,查找到范圍的下限(3)

通過鏈表指針遍歷

總結(jié)厢绝，B+樹比B樹更適合做數(shù)據(jù)庫索引：

1）B+樹的磁盤讀寫代價更低

? ? ? ?B+樹的內(nèi)部結(jié)點并沒有指向關(guān)鍵字具體信息的指針昔汉。因此其內(nèi)部結(jié)點相對B 樹更小挤庇。如果把所有同一內(nèi)部結(jié)點的關(guān)鍵字存放在同一盤塊中嫡秕，那么盤塊所能容納的關(guān)鍵字數(shù)量也越多昆咽。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多掷酗。相對來說IO讀寫次數(shù)也就降低了泻轰；

2）B+樹查詢效率更加穩(wěn)定
? ? ? ?由于非終結(jié)點并不是最終指向文件內(nèi)容的結(jié)點浮声，而只是葉子結(jié)點中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點到葉子結(jié)點的路至朗。所有關(guān)鍵字查詢的路徑長度相同，導致每一個數(shù)據(jù)的查詢效率相當唆香；

3）B+樹便于范圍查詢（最重要的原因躬它，范圍查找是數(shù)據(jù)庫的常態(tài)）
? ? ? ?B樹在提高了IO性能的同時并沒有解決元素遍歷的我效率低下的問題虑凛，正是為了解決這個問題桑谍，B+樹應(yīng)用而生锣披。B+樹只需要去遍歷葉子節(jié)點就可以實現(xiàn)整棵樹的遍歷雹仿。而且在數(shù)據(jù)庫中基于范圍的查詢是非常頻繁的胧辽，而B樹不支持這樣的操作或者說效率太低邑商；
? ? ? ?Mysql數(shù)據(jù)庫中人断，大多數(shù)存儲引擎都使用這種索引恶迈，存儲引擎以不同的方式使用B+Tree索引暇仲，性能也各不相同熔吗，各有優(yōu)劣，如轿秧，MyISAM使用前綴壓縮技術(shù)使得索引更小菇篡，但InnoDB按照原數(shù)據(jù)格式進行存儲驱还。再如MyISAM索引通過數(shù)據(jù)的物理位置引用被索引的行议蟆，而InnoDB通過主鍵引用被索引的行咐容。
? ? ? ?后面這句話什么意思呢路狮？MyISAM索引文件和數(shù)據(jù)文件是分離的奄妨，索引文件僅保存記錄所在頁的指針砸抛，通過這些指針指向的物理地址來讀取頁锰悼，進而讀取索引的行箕般。

? ? ? ?InnoDB存儲引擎采用“聚集“索引的數(shù)據(jù)存儲方式實現(xiàn)丝里，所謂聚集杯聚，就是指數(shù)據(jù)行和相鄰的鍵值緊湊的存儲在一起幌绍。在InnoDB中颁独，表數(shù)據(jù)本身就是按B+Tree組織的一個索引結(jié)構(gòu)誓酒，這棵樹的葉節(jié)點data域完整的保存了數(shù)據(jù)記錄靠柑。

可以使用B+樹索引的查詢類型

? ? ? ?B+樹索引能夠加快訪問數(shù)據(jù)的速度歼冰，因為存儲引擎不再需要進行全表掃描來獲取需要的數(shù)據(jù)停巷，取而代之的是從索引的根節(jié)點開始進行搜索畔勤。根節(jié)點的槽中存放了指向子節(jié)點的指針庆揪，存儲引擎根據(jù)這些指針向下層查找缸榛。B+樹對索引列hi順序組織數(shù)據(jù)的内颗，所以很適合查找范圍數(shù)據(jù)均澳，其實工作中大部分查詢語句都是范圍查找找前。

例如躺盛，創(chuàng)建表:

CREATE TABLE `people` (
  `last_name` varchar(50) CHARACTER SET utf8 NOT NULL,
  `first_name` varchar(50) CHARACTER SET utf8 NOT NULL,
  `dob` date NOT NULL,
  `gender` enum('m','f') CHARACTER SET utf8 NOT NULL,
  KEY `myindex` (`last_name`,`first_name`,`dob`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=latin1 ROW_FORMAT=COMPACT;

數(shù)據(jù)的B+Tree排列方式：

索引排列順序依據(jù)索引創(chuàng)建時列的順序周叮。
? ? ? ?并不是所有的查詢都能使用到B+樹索引则吟，B+樹索引適用于全鍵值、鍵值范圍或鍵前綴查找等得糜，其中鍵前綴查找只適合用于根據(jù)最左前綴的查找朝抖。

1. 全值匹配
   和索引中所有的列進行匹配治宣，例如查詢姓名是Cuba Allen侮邀、出生于1960-01-01的人绊茧。

SELECT * FROM `people` where last_name='Allen' and first_name="Cuba" and dob="1960-01-01"

2.匹配最左前綴

查找所有姓為Allen的人华畏，即只使用索引的第一列亡笑。

SELECT  *  FROM  `people`  where last_name='Allen'

3.匹配列前綴

查找所有姓以A開頭的人仑乌。即只使用索引的第一列

SELECT  *  FROM  `people`  where last_name like 'B%'

4.匹配范圍值

查找姓在Allen和Barrymore之間的人叶撒。

SELECT  *  FROM  `people` where last_name >= 'Allen' and last_name <='Barrymore'

5.精確匹配某一列并范圍匹配另一列

查找姓為Allen祠够，并且名字是字母K開頭的人古瓤。即第一列l(wèi)ast_name全匹配腺阳，第二列first_name范圍匹配

select * from people where last_name='Allen' and first_name like 'K%'

6.只訪問索引的查詢

? ? ? ?查詢只需要訪問索引，而無需訪問數(shù)據(jù)行皮获，后面會單獨討論這種覆蓋索引的優(yōu)化。
? ? ? ?另购公，索引節(jié)點是有序鏈表宏浩，索引除了按值查找外比庄，還可以用于查詢中的order by 操作佳窑，即按順序查找华嘹，前提是Order by 滿足上述幾種查詢類型法竞。
? ? ? ?如:

select * from people where last_name='Allen' order by last_name 

B+Tree索引的限制

• 如果不是按照索引的最左列開始查找薛躬，則無法使用索引型宝。

例如上述例子絮爷，索引無法用于查找名字為Bill的人坑夯，也無法用于查找某個特定生日的人柜蜈。

• 如果查詢中有某個列的范圍查詢，則右邊所有列都無法使用索引優(yōu)化查詢藻雪。

 select * from people where last_name='Allen' and first_name like 'J%' and dob='1976-12-23'

這個查詢只能使用索引的前兩列勉耀，原因是后面列的排序是建立在前列完全一致的基礎(chǔ)上的瑰排。

• 不能跳過索引中的列

  如，上述索引無法用于查找姓為Allen且出生日期是1960-01-01的人崇渗。如果不指出第二列first_name宅广，那么mysql只能會用索引的第一列跟狱。

select  *   from people  where last_name = 'Allen'  and dob='1960-01-01'

總結(jié)：索引列的順序太重要了驶臊，牢記B+樹的核心：“有序鏈表且按列順序排列”。