1. 最簡(jiǎn)單的索引
假設(shè)查詢id=4這條數(shù)據(jù),在沒(méi)有索引的前提下,只能全表掃描。
現(xiàn)在就需要針對(duì)主鍵設(shè)計(jì)一個(gè)索引羹令,這個(gè)索引實(shí)際上就是主鍵目錄鲤屡。
主鍵目錄就是把數(shù)據(jù)頁(yè)的頁(yè)號(hào)
,還有數(shù)據(jù)頁(yè)里面最小的主鍵值
放在一起福侈,組成一個(gè)索引的目錄酒来。
有了主鍵目錄,再通過(guò)主鍵去查詢數(shù)據(jù)不就方便了肪凛。假設(shè)現(xiàn)在需要查詢id=3的數(shù)據(jù)堰汉,首先會(huì)跟主鍵目錄里面的最小主鍵對(duì)比,也即是跟每個(gè)數(shù)據(jù)頁(yè)的最小主鍵對(duì)比伟墙,發(fā)現(xiàn)id=3大于數(shù)據(jù)頁(yè)2的最小主鍵值1翘鸭,小于數(shù)據(jù)頁(yè)8的最大主鍵值4。
說(shuō)明id=3的數(shù)據(jù)一定是在數(shù)據(jù)頁(yè)2里面戳葵。
這就是最簡(jiǎn)單最基礎(chǔ)的索引概念就乓。
2. 基于B+樹(shù)實(shí)現(xiàn)的索引頁(yè)的物理存儲(chǔ)結(jié)構(gòu)
我們已經(jīng)知道了主鍵目錄實(shí)現(xiàn)的索引,現(xiàn)在有一個(gè)問(wèn)題,如果單表的數(shù)據(jù)過(guò)于龐大生蚁,達(dá)到幾百萬(wàn)幾千萬(wàn)甚至上億噩翠。這時(shí)候再在主鍵目錄存放大量的數(shù)據(jù)頁(yè)和最小主鍵值怎么行呢?
這個(gè)時(shí)候邦投,就是采取把索引數(shù)據(jù)存儲(chǔ)在數(shù)據(jù)頁(yè)里的方式來(lái)解決伤锚。
即是說(shuō),表里的實(shí)際數(shù)據(jù)是存放在數(shù)據(jù)頁(yè)里志衣,索引的數(shù)據(jù)也存儲(chǔ)在頁(yè)里屯援。
此時(shí)的索引頁(yè)存儲(chǔ)的是最小主鍵和數(shù)據(jù)頁(yè)號(hào)。
當(dāng)數(shù)據(jù)頁(yè)越來(lái)越多蠢涝,索引頁(yè)也會(huì)越來(lái)越多玄呛,想再通過(guò)索引頁(yè)去查詢對(duì)應(yīng)數(shù)據(jù)頁(yè)效率就變得非常低下。
此時(shí)在索引頁(yè)多加一個(gè)層級(jí)和二,在更高級(jí)的層級(jí)里徘铝,保存了每個(gè)索引頁(yè)的頁(yè)號(hào)
和頁(yè)里的最小主鍵值
。
假設(shè)現(xiàn)在要找id=46的數(shù)據(jù)惯吕,首先到索引頁(yè)35里找惕它,通過(guò)二分法快速定位到應(yīng)該到索引頁(yè)20里去找。再?gòu)乃饕?yè)20里面通過(guò)二分法查找定位废登,就會(huì)發(fā)現(xiàn)id=46的數(shù)據(jù)是在數(shù)據(jù)頁(yè)8里面淹魄,通過(guò)目錄頁(yè)二分查找,查詢到id=46這行數(shù)據(jù)堡距。
如果最頂層的索引頁(yè)里面存放的下層索引頁(yè)過(guò)多甲锡,則需要再次分層
這時(shí)候的索引頁(yè)結(jié)構(gòu)就是一種樹(shù)結(jié)構(gòu)。非葉節(jié)點(diǎn)的索引頁(yè)存放的是索引頁(yè)的頁(yè)號(hào)
和最小主鍵值
羽戒,葉節(jié)點(diǎn)的索引頁(yè)存放的是數(shù)據(jù)頁(yè)
和最小主鍵值
缤沦。
3. 聚簇索引
通過(guò)索引頁(yè)的物理存儲(chǔ)結(jié)構(gòu)我們知道了是如何通過(guò)主鍵索引查詢數(shù)據(jù)。
也就是說(shuō)易稠,通過(guò)主鍵的二分查找缸废,找到對(duì)應(yīng)的葉節(jié)點(diǎn)的索引頁(yè),然后二分查找對(duì)應(yīng)的數(shù)據(jù)頁(yè)驶社,通過(guò)頁(yè)目錄企量,二分查找對(duì)應(yīng)的槽位,然后遍歷槽位中的數(shù)據(jù)得到相應(yīng)的數(shù)據(jù)行亡电。
也可以說(shuō) 葉節(jié)點(diǎn)的索引頁(yè)就是數(shù)據(jù)頁(yè)自己本身届巩。
這也是索引頁(yè)+數(shù)據(jù)頁(yè)組成的B+樹(shù)的聚簇索引
。
所以份乒,在innodb引擎里面姆泻,對(duì)數(shù)據(jù)的增刪改時(shí)零酪,就是直接把數(shù)據(jù)頁(yè)放到聚簇索引里,數(shù)據(jù)就在聚簇索引里拇勃,聚簇索引就包含了數(shù)據(jù)四苇。
發(fā)生頁(yè)分裂時(shí),各個(gè)數(shù)據(jù)頁(yè)內(nèi)部就會(huì)調(diào)整數(shù)據(jù)行方咆,保證數(shù)據(jù)頁(yè)內(nèi)的主鍵值都是有順序的月腋,下一個(gè)數(shù)據(jù)頁(yè)的所有主鍵值都大于上一個(gè)數(shù)據(jù)頁(yè)的所有主鍵值。
在頁(yè)分裂的同時(shí)也會(huì)維護(hù)上層的索引數(shù)據(jù)結(jié)構(gòu)瓣赂。在上層的索引頁(yè)里維護(hù)你的索引條目榆骚。如果數(shù)據(jù)頁(yè)越來(lái)越多,對(duì)應(yīng)的索引頁(yè)放不下了煌集,此時(shí)就會(huì)出現(xiàn)新的索引頁(yè)同時(shí)再搞一個(gè)上層的索引頁(yè)妓肢。
4. 二級(jí)索引
假設(shè)要針對(duì)其他字段建立索引,例如name苫纤、age之類的字段碉钠,都是類似的。
現(xiàn)在要對(duì)name字段建立一個(gè)索引卷拘,那么此時(shí)插入是數(shù)據(jù)的時(shí)候喊废,一方面會(huì)把完整的數(shù)據(jù)插入到聚簇索引的葉節(jié)點(diǎn)的數(shù)據(jù)頁(yè)里去,另一方面會(huì)為name字段重新生成一棵B+樹(shù)栗弟,這棵B+樹(shù)的葉節(jié)點(diǎn)也是數(shù)據(jù)頁(yè)污筷,但是這個(gè)數(shù)據(jù)頁(yè)里面僅僅存放主鍵字段
和name字段
這是一棵獨(dú)立于聚簇索引的B+樹(shù),是根據(jù)name字段構(gòu)建的索引B+樹(shù)乍赫。至于葉節(jié)點(diǎn)的數(shù)據(jù)頁(yè)的排序規(guī)則瓣蛀,和之前的一樣,根據(jù)name值的大小排序雷厂。同時(shí)下一個(gè)數(shù)據(jù)頁(yè)里的name字段值都大于上一個(gè)數(shù)據(jù)頁(yè)里的name字段值惋增。
這棵B+樹(shù)中,非葉節(jié)點(diǎn)存儲(chǔ)的是索引頁(yè)號(hào)
和最小name字段值
罗侯;葉節(jié)點(diǎn)存儲(chǔ)的是主鍵字段
和name字段值
這是基于name字段值來(lái)搜索數(shù)據(jù)時(shí),搜索過(guò)程是一致的溪猿,從根節(jié)點(diǎn)層層往下找钩杰,通過(guò)二分查找快速定位所在數(shù)據(jù)頁(yè)。
假設(shè)是“select * from user where name = 'zangsan'”這樣一條查詢诊县,首先會(huì)根據(jù)name字段值在name字段的索引b+樹(shù)里面找讲弄,找到葉節(jié)點(diǎn)也僅僅找到對(duì)應(yīng)的主鍵值,但并沒(méi)有找到該行數(shù)據(jù)依痊。
接下來(lái)還需要進(jìn)行回表
避除。還需要根據(jù)主鍵值怎披,再到聚簇索引里從根節(jié)點(diǎn)開(kāi)始,一路找到葉節(jié)點(diǎn)的數(shù)據(jù)頁(yè)瓶摆,定位到主鍵對(duì)應(yīng)的完整數(shù)據(jù)行凉逛。此時(shí)才能將 select * 要的全部字段返回。
所以群井,這種根據(jù)普通字段建立的索引稱為二級(jí)索引状飞。
注明:
學(xué)習(xí)筆記總結(jié)于公棕號(hào):儒猿技術(shù)窩。感興趣的同學(xué)可以前往關(guān)注书斜。