一句話簡單的來說建丧，索引的出現(xiàn)其實就是為了提高數(shù)據(jù)查詢的效率排龄，就像書的目錄一樣。對于數(shù)據(jù)庫的表而言翎朱，索引其實就是它的目錄橄维。
索引的常見模型
索引的出現(xiàn)是為了提高查詢效率，但實現(xiàn)索引的方式卻有很多種拴曲，所以這里也就引入了索引模型的概念争舞。可以用于提高讀寫效率的數(shù)據(jù)結(jié)構(gòu)有很多澈灼，這里介紹三種常見竞川、比較簡單的數(shù)據(jù)結(jié)構(gòu)，他們是哈希表叁熔、有序數(shù)組委乌、和搜索樹。
從使用的角度荣回，簡單說下三種索引的區(qū)別福澡。
哈希表是一種以key-value存儲的數(shù)據(jù)結(jié)構(gòu)。哈希的思路很簡單驹马，把value存放在數(shù)組里革砸，用一個哈希函數(shù)把key換算成一個確定的位置除秀。然后把value存放在數(shù)組的這個位置。
需要注意的是算利，hash的key并不是遞增的册踩，這樣的好處是增加新的數(shù)據(jù)時速度會很快，只需要往后追加效拭，缺點是暂吉，因為不是有序的，所以哈希索引做區(qū)間查詢的速度是很慢的缎患。
所以哈希這種結(jié)構(gòu)只適用于只有等值查詢的這種場景慕的。
而有序數(shù)組在范圍查詢和等值查詢的場景中性能都非常優(yōu)秀。
如果僅僅看查詢效率挤渔，有序數(shù)組就是最好的數(shù)據(jù)結(jié)構(gòu)了肮街，但是需要更新數(shù)據(jù)的時候就麻煩了，你往中間插一個記錄就必須的挪動后面所有的記錄判导，成本太高嫉父。
所以，有序數(shù)組只適用于靜態(tài)存儲引擎眼刃，比如你要保存的是2017年所有人口的信息绕辖。
二叉搜索樹是課本里經(jīng)典的數(shù)據(jù)結(jié)構(gòu)了，結(jié)構(gòu)不在贅述擂红。
樹可以有二叉仪际，也可以有多叉，二叉樹是搜索效率最高的昵骤，但實際上大多存儲引擎并不使用二叉樹弟头，其原因是索引不僅存在內(nèi)存中，還要寫到磁盤上涉茧。
你可以想象一下，一顆100萬節(jié)點的平衡二叉樹疹娶，樹高20伴栓，一次查詢可能需要訪問20個數(shù)據(jù)塊。在機(jī)械硬盤的時代雨饺，從磁盤隨機(jī)訪問一個數(shù)據(jù)塊大概需要10ms的尋址時間钳垮，使用二叉樹存儲，單獨(dú)訪問一個行可能需要20*10ms的時間额港。
為了讓一個查詢盡量的少讀磁盤饺窿，就必須讓查詢查詢過程訪問盡量少的數(shù)據(jù)塊。那么我們就不應(yīng)該使用二叉樹移斩，而是使用“N叉樹”肚医，這個N取決于數(shù)據(jù)塊的大小绢馍。
InnoDB的索引模型
在InnoDB中，表都是根據(jù)主鍵順序以索引方式存放的肠套，這種存儲的方式表被稱為索引組織表舰涌。InnoDB使用了B+樹存儲模型，所以索引都是存儲在B+樹中的你稚。
每一個索引在DB里面對應(yīng)一顆B+樹瓷耙。
假設(shè)我們有一個主鍵為ID的表，表中有字段K刁赖，并且在K上有索引搁痛。
這個表的建表語句是
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
從圖中不難看出，根據(jù)葉子節(jié)點的內(nèi)容宇弛，索引類型分為主鍵索引和非主鍵索引鸡典。
主鍵索引的葉子節(jié)點存的是整行數(shù)據(jù)。在InnoDB里涯肩，主鍵索引也被稱為聚簇索引（clustered index）轿钠。
非主鍵索引葉子節(jié)點內(nèi)容是主鍵的值，在InnoDB里非主鍵索性也被稱為二級索引病苗。
基于上述結(jié)構(gòu)疗垛，我們來討論一個問題:基于主鍵索引和非主鍵索引的查詢有什么區(qū)別
- 如果語句是
select * from T WHERE ID=500;即主鍵查詢方式，則只需要搜索ID這棵B+樹硫朦。 - 如果查詢語句是
select * from T where k=5;即普通索引查詢方式贷腕，則需要先搜索K索引樹，得到ID的值為500咬展，再到ID索引樹搜索一次泽裳。這個過程稱為回表。
也就是說基于非主鍵的索引要多掃描一顆索引樹破婆。因此涮总，我們在應(yīng)用中應(yīng)該盡量使用主鍵索引。
索引維護(hù)
以上面這個圖為例祷舀，如果新插入的行ID為700瀑梗，則只需要在R5的后面插入一條新記錄;如果新插入的值ID為400，則相對麻煩了裳扯，需要邏輯上挪動后面的數(shù)據(jù)抛丽，空出位置。
更糟糕的情況是饰豺，如果R5所在的數(shù)據(jù)頁已經(jīng)滿了亿鲜，這時候就需要申請一個新的數(shù)據(jù)頁，挪動部分?jǐn)?shù)據(jù)過去冤吨。這個過程稱為頁分裂蒿柳。在這種情況下饶套，性能會受到影響。
當(dāng)然有分裂就會有合并其馏，當(dāng)相鄰兩個頁由于刪除了數(shù)據(jù)利用率很低后凤跑，會將數(shù)據(jù)頁做合并。
基于上面的維護(hù)過程叛复，我們來討論一個問題:
你可能在一些建表規(guī)范里見過一些類似描述仔引，要求建表語句里一定要有自增主鍵。當(dāng)然事無絕對褐奥，我們來分析一下哪些場景下應(yīng)該使用自增主鍵咖耘，而哪些場景下不應(yīng)該。
- 自增主鍵的插入模式撬码，符合了我們前面提到的遞增插入場景儿倒。不會觸發(fā)頁分裂。而業(yè)務(wù)邏輯字段作為主鍵呜笑，往往不容易保證由于插入夫否，這樣寫數(shù)據(jù)的成本相對較高。
- 除了考慮性能外叫胁，我們還可以從存儲空間的角度來看凰慈。假設(shè)你的表中確實有一個唯一字段，比如字符串類型的身份證號驼鹅，那應(yīng)該用身份證號做主鍵微谓，還是用自增主鍵呢？
由于每個非主鍵索引葉子節(jié)點上都是主鍵索引的值输钩。如果用身份證號做主鍵豺型，那么每個二級索引的葉子節(jié)點占用約20個字節(jié)，而如果用整形做主鍵买乃，則只需要4個字節(jié)姻氨。
顯然，主鍵長度越小剪验，普通索引的葉子節(jié)點就越小肴焊，普通索引占用的空間也就越小。
所以從性能和存儲空間方面考量碉咆，自增主鍵往往是更合理的選擇。
有沒有什么場景適合用業(yè)務(wù)字段直接做主鍵的呢蛀恩？ 還是有的疫铜。比如有些業(yè)務(wù)場景需求是這樣的:
- 只有一個索引;
- 該索引必須是唯一索引。
你也一定看出來了双谆，這就是典型的kv場景壳咕。由于沒有其他索引席揽，所以也就不用考慮其他索引的葉子節(jié)點大小問題。
延伸閱讀
了解change buffer作用
感謝以下文章作者:
https://blog.csdn.net/shenjian58/article/details/93691224
https://www.lizenghai.com/archives/43575.html
