參考：https://zhuanlan.zhihu.com/p/23624390
https://tech.meituan.com/mysql-index.html
前兩天稍微研究了下數據庫索引，但是只是看了看一些文章心墅，并沒有動手實踐构眯，哎呀调鲸，這也是最近覺得郁悶的事秸弛，現在的工作太無聊裁厅，很多想研究的東西只能晚上回家實踐柔昼，但有時候覺得暫時用不到就會先擱置一邊馍乙。布近。垫释。
簡介
網上很多講解索引的文章對索引的描述是這樣的「索引就像書的目錄， 通過書的目錄就準確的定位到了書籍具體的內容」吊输，這句話描述的非常正確饶号， 但就像脫了褲子放屁，說了跟沒說一樣季蚂，通過目錄查找書的內容自然是要比一頁一頁的翻書找來的快茫船，同樣使用的索引的人難到會不知道，通過索引定位到數據比直接一條一條的查詢來的快扭屁，不然他們?yōu)槭裁匆ㄋ饕?/p>
其實算谈，我們的漢語字典的正文本身就是一個聚集索引。比如料滥，我們要查“安”字然眼，就會很自然地翻開字典的前幾頁，因為“安”的拼音是“an”葵腹，而按照拼音排序漢字的字典是以英文字母“a”開頭并以“z”結尾的高每，那么“安”字就自然地排在字典的前部。如果您翻完了所有以“a”開頭的部分仍然找不到這個字践宴，那么就說明您的字典中沒有這個字鲸匿；同樣的，如果查“張”字阻肩，那您也會將您的字典翻到最后部分带欢，因為“張”的拼音是“zhang”。也就是說烤惊，字典的正文部分本身就是一個目錄乔煞，您不需要再去查其他目錄來找到您需要找的內容。我們把這種正文內容本身就是一種按照一定規(guī)則排列的目錄稱為“聚集索引”柒室。
如果您認識某個字渡贾，您可以快速地從自動中查到這個字。但您也可能會遇到您不認識的字雄右，不知道它的發(fā)音剥啤，這時候，您就不能按照剛才的方法找到您要查的字不脯，而需要去根據“偏旁部首”查到您要找的字，然后根據這個字后的頁碼直接翻到某頁來找到您要找的字刻诊。但您結合“部首目錄”和“檢字表”而查到的字的排序并不是真正的正文的排序方法防楷，比如您查“張”字，我們可以看到在查部首之后的檢字表中“張”的頁碼是672頁则涯，檢字表中“張”的上面是“馳”字复局，但頁碼卻是63頁冲簿，“張”的下面是“弩”字，頁面是390頁亿昏。很顯然峦剔，這些字并不是真正的分別位于“張”字的上下方，現在您看到的連續(xù)的“馳角钩、張吝沫、弩”三字實際上就是他們在非聚集索引中的排序，是字典正文中的字在非聚集索引中的映射递礼。我們可以通過這種方式來找到您所需要的字惨险，但它需要兩個過程，先找到目錄中的結果脊髓，然后再翻到您所需要的頁碼辫愉。我們把這種目錄純粹是目錄，正文純粹是正文的排序方式稱為“非聚集索引”将硝。
想要理解索引原理必須清楚一種數據結構「平衡樹」(非二叉)恭朗，也就是b tree或者 b+ tree，重要的事情說三遍：“平衡樹依疼，平衡樹痰腮，平衡樹”。當然涛贯， 有的數據庫也使用哈希桶作用索引的數據結構 诽嘉， 然而， 主流的RDBMS都是把平衡樹當做數據表默認的索引數據結構的弟翘。
聚集索引
我們平時建表的時候都會為表加上主鍵虫腋， 在某些關系數據庫中， 如果建表時不指定主鍵稀余，數據庫會拒絕建表的語句執(zhí)行悦冀。 事實上， 一個加了主鍵的表睛琳，并不能被稱之為「表」盒蟆。一個沒加主鍵的表，它的數據無序的放置在磁盤存儲器上师骗，一行一行的排列的很整齊历等， 跟我認知中的「表」很接近。如果給表上了主鍵辟癌，那么表在磁盤上的存儲結構就由整齊排列的結構轉變成了樹狀結構寒屯，也就是上面說的「平衡樹」結構，換句話說，就是整個表就變成了一個索引寡夹。沒錯处面， 再說一遍， 整個表變成了一個索引菩掏，也就是所謂的「聚集索引」魂角。 這就是為什么一個表只能有一個主鍵， 一個表只能有一個「聚集索引」智绸，因為主鍵的作用就是把「表」的數據格式轉換成「索引（平衡樹）」的格式放置野揪。
上圖就是帶有主鍵的表（聚集索引）的結構圖。圖畫的不是很好传于， 將就著看囱挑。其中樹的所有結點（底部除外）的數據都是由主鍵字段中的數據構成，也就是通常我們指定主鍵的id字段沼溜。最下面部分是真正表中的數據平挑。 假如我們執(zhí)行一個SQL語句：
select * from table where id = 1256;
首先根據索引定位到1256這個值所在的葉結點，然后再通過葉結點取到id等于1256的數據行系草。 這里不講解平衡樹的運行細節(jié)通熄， 但是從上圖能看出，樹一共有三層找都， 從根節(jié)點至葉節(jié)點只需要經過三次查找就能得到結果唇辨。如下圖
假如一張表有一億條數據 ，需要查找其中某一條數據能耻，按照常規(guī)邏輯赏枚， 一條一條的去匹配的話， 最壞的情況下需要匹配一億次才能得到結果晓猛，用大O標記法就是O(n)最壞時間復雜度饿幅，這是無法接受的，而且這一億條數據顯然不能一次性讀入內存供程序使用戒职， 因此袒哥， 這一億次匹配在不經緩存優(yōu)化的情況下就是一億次IO開銷鞍陨，以現在磁盤的IO能力和CPU的運算能力侠仇， 有可能需要幾個月才能得出結果 脐湾。如果把這張表轉換成平衡樹結構（一棵非常茂盛和節(jié)點非常多的樹），假設這棵樹有10層捧韵，那么只需要10次IO開銷就能查找到所需要的數據市咆， 速度以指數級別提升，用大O標記法就是O(log n)再来，n是記錄總樹床绪，底數是樹的分叉數，結果就是樹的層次數。換言之癞己，查找次數是以樹的分叉數為底，記錄總數的對數梭伐，用公式來表示就是
用程序來表示就是Math.Log(100000000,10)痹雅，100000000是記錄數，10是樹的分叉數（真實環(huán)境下分叉數遠不止10）糊识， 結果就是查找次數绩社，這里的結果從億降到了個位數。因此赂苗，利用索引會使數據庫查詢有驚人的性能提升愉耙。
然而， 事物都是有兩面的拌滋， 索引能讓數據庫查詢數據的速度上升朴沿， 而使寫入數據的速度下降，原因很簡單的败砂， 因為平衡樹這個結構必須一直維持在一個正確的狀態(tài)赌渣， 增刪改數據都會改變平衡樹各節(jié)點中的索引數據內容，破壞樹結構昌犹， 因此坚芜，在每次數據改變時， DBMS必須去重新梳理樹（索引）的結構以確保它的正確斜姥，這會帶來不小的性能開銷鸿竖，也就是為什么索引會給查詢以外的操作帶來副作用的原因。
非聚集索引
講完聚集索引 铸敏， 接下來聊一下非聚集索引缚忧， 也就是我們平時經常提起和使用的常規(guī)索引。
非聚集索引和聚集索引一樣搞坝， 同樣是采用平衡樹作為索引的數據結構搔谴。索引樹結構中各節(jié)點的值來自于表中的索引字段， 假如給user表的name字段加上索引 桩撮， 那么索引就是由name字段中的值構成敦第，在數據改變時， DBMS需要一直維護索引結構的正確性店量。如果給表中多個字段加上索引 芜果， 那么就會出現多個獨立的索引結構，每個索引（非聚集索引）互相之間不存在關聯(lián)融师。 如下圖
每次給字段建一個新索引右钾， 字段中的數據就會被復制一份出來， 用于生成索引。 因此舀射， 給表添加索引窘茁，會增加表的體積， 占用磁盤存儲空間脆烟。
非聚集索引和聚集索引的區(qū)別在于山林， 通過聚集索引可以查到需要查找的數據， 而通過非聚集索引可以查到記錄對應的主鍵值 邢羔， 再使用主鍵的值通過聚集索引查找到需要的數據驼抹，如下圖
不管以任何方式查詢表， 最終都會利用主鍵通過聚集索引來定位到數據拜鹤， 聚集索引（主鍵）是通往真實數據所在的唯一路徑框冀。
然而， 有一種例外可以不使用聚集索引就能查詢出所需要的數據敏簿， 這種非主流的方法 稱之為「覆蓋索引」查詢明也， 也就是平時所說的復合索引或者多字段索引查詢。 文章上面的內容已經指出极谊， 當為字段建立索引以后诡右， 字段中的內容會被同步到索引之中， 如果為一個索引指定兩個字段轻猖， 那么這個兩個字段的內容都會被同步至索引之中帆吻。
先看下面這個SQL語句
建立索引
create index index_birthday on user_info(birthday);
查詢生日在1991年11月1日出生用戶的用戶名
select user_name from user_info where birthday = '1991-11-1'
這句SQL語句的執(zhí)行過程如下
首先，通過非聚集索引index_birthday查找birthday等于1991-11-1的所有記錄的主鍵ID值
然后咙边，通過得到的主鍵ID值執(zhí)行聚集索引查找猜煮，找到主鍵ID值對就的真實數據（數據行）存儲的位置
最后， 從得到的真實數據中取得user_name字段的值返回败许， 也就是取得最終的結果
我們把birthday字段上的索引改成雙字段的覆蓋索引
create index index_birthday_and_user_name on user_info(birthday, user_name);
這句SQL語句的執(zhí)行過程就會變?yōu)?/p>
通過非聚集索引index_birthday_and_user_name查找birthday等于1991-11-1的葉節(jié)點的內容王带，然而， 葉節(jié)點中除了有user_name表主鍵ID的值以外市殷， user_name字段的值也在里面愕撰， 因此不需要通過主鍵ID值的查找數據行的真實所在， 直接取得葉節(jié)點中user_name的值返回即可醋寝。 通過這種覆蓋索引直接查找的方式搞挣， 可以省略不使用覆蓋索引查找的后面兩個步驟， 大大的提高了查詢性能音羞，如下圖
數據庫索引的大致工作原理就是像文中所述囱桨， 然而細節(jié)方面可能會略有偏差，這但并不會對概念闡述的結果產生影響嗅绰。
索引目的
索引的目的在于提高查詢效率舍肠，可以類比字典搀继，如果要查“mysql”這個單詞，我們肯定需要定位到m字母翠语，然后從下往下找到y(tǒng)字母叽躯，再找到剩下的sql。如果沒有索引肌括，那么你可能需要把所有單詞看一遍才能找到你想要的险毁，如果我想找到m開頭的單詞呢？或者ze開頭的單詞呢们童？是不是覺得如果沒有索引，這個事情根本無法完成鲸鹦？
索引原理
除了詞典慧库，生活中隨處可見索引的例子，如火車站的車次表馋嗜、圖書的目錄等齐板。它們的原理都是一樣的，通過不斷的縮小想要獲得數據的范圍來篩選出最終想要的結果葛菇，同時把隨機的事件變成順序的事件甘磨，也就是我們總是通過同一種查找方式來鎖定數據。
數據庫也是一樣眯停，但顯然要復雜許多济舆，因為不僅面臨著等值查詢，還有范圍查詢(>莺债、<滋觉、between、in)齐邦、模糊查詢(like)椎侠、并集查詢(or)等等。數據庫應該選擇怎么樣的方式來應對所有的問題呢措拇？我們回想字典的例子我纪，能不能把數據分成段，然后分段查詢呢丐吓？最簡單的如果1000條數據浅悉，1到100分成第一段，101到200分成第二段汰蜘，201到300分成第三段......這樣查第250條數據仇冯，只要找第三段就可以了，一下子去除了90%的無效數據族操。但如果是1千萬的記錄呢苛坚，分成幾段比較好比被？稍有算法基礎的同學會想到搜索樹，其平均復雜度是lgN泼舱，具有不錯的查詢性能等缀。但這里我們忽略了一個關鍵的問題，復雜度模型是基于每次相同的操作成本來考慮的娇昙，數據庫實現比較復雜尺迂，數據保存在磁盤上，而為了提高性能冒掌，每次又可以把部分數據讀入內存來計算噪裕，因為我們知道訪問磁盤的成本大概是訪問內存的十萬倍左右，所以簡單的搜索樹難以滿足復雜的應用場景股毫。
磁盤IO與預讀
前面提到了訪問磁盤膳音，那么這里先簡單介紹一下磁盤IO和預讀，磁盤讀取數據靠的是機械運動铃诬，每次讀取數據花費的時間可以分為尋道時間祭陷、旋轉延遲、傳輸時間三個部分趣席，尋道時間指的是磁臂移動到指定磁道所需要的時間兵志，主流磁盤一般在5ms以下；旋轉延遲就是我們經常聽說的磁盤轉速宣肚，比如一個磁盤7200轉想罕，表示每分鐘能轉7200次，也就是說1秒鐘能轉120次钉寝，旋轉延遲就是1/120/2 = 4.17ms弧呐；傳輸時間指的是從磁盤讀出或將數據寫入磁盤的時間，一般在零點幾毫秒嵌纲，相對于前兩個時間可以忽略不計俘枫。那么訪問一次磁盤的時間，即一次磁盤IO的時間約等于5+4.17 = 9ms左右逮走，聽起來還挺不錯的鸠蚪，但要知道一臺500 -MIPS的機器每秒可以執(zhí)行5億條指令，因為指令依靠的是電的性質师溅，換句話說執(zhí)行一次IO的時間可以執(zhí)行40萬條指令茅信，數據庫動輒十萬百萬乃至千萬級數據，每次9毫秒的時間墓臭，顯然是個災難蘸鲸。下圖是計算機硬件延遲的對比圖，供大家參考：
考慮到磁盤IO是非常高昂的操作窿锉，計算機操作系統(tǒng)做了一些優(yōu)化酌摇，當一次IO時膝舅，不光把當前磁盤地址的數據，而是把相鄰的數據也都讀取到內存緩沖區(qū)內窑多，因為局部預讀性原理告訴我們仍稀，當計算機訪問一個地址的數據的時候，與其相鄰的數據也會很快被訪問到埂息。每一次IO讀取的數據我們稱之為一頁(page)技潘。具體一頁有多大數據跟操作系統(tǒng)有關，一般為4k或8k千康，也就是我們讀取一頁內的數據時候享幽，實際上才發(fā)生了一次IO，這個理論對于索引的數據結構設計非常有幫助拾弃。
索引的數據結構
前面講了生活中索引的例子琉闪，索引的基本原理，數據庫的復雜性砸彬，又講了操作系統(tǒng)的相關知識，目的就是讓大家了解斯入，任何一種數據結構都不是憑空產生的砂碉，一定會有它的背景和使用場景，我們現在總結一下刻两，我們需要這種數據結構能夠做些什么增蹭，其實很簡單，那就是：每次查找數據時把磁盤IO次數控制在一個很小的數量級磅摹，最好是常數數量級滋迈。那么我們就想到如果一個高度可控的多路搜索樹是否能滿足需求呢？就這樣户誓，b+樹應運而生饼灿。
詳解b+樹
如上圖，是一顆b+樹帝美，關于b+樹的定義可以參見B+樹碍彭，這里只說一些重點，淺藍色的塊我們稱之為一個磁盤塊悼潭，可以看到每個磁盤塊包含幾個數據項（深藍色所示）和指針（黃色所示）庇忌，如磁盤塊1包含數據項17和35，包含指針P1舰褪、P2皆疹、P3，P1表示小于17的磁盤塊占拍，P2表示在17和35之間的磁盤塊略就，P3表示大于35的磁盤塊捎迫。真實的數據存在于葉子節(jié)點即3、5残制、9立砸、10、13初茶、15颗祝、28、29恼布、36螺戳、60、75折汞、79倔幼、90、99爽待。非葉子節(jié)點只不存儲真實的數據损同，只存儲指引搜索方向的數據項，如17鸟款、35并不真實存在于數據表中膏燃。
b+樹的查找過程
如圖所示，如果要查找數據項29何什，那么首先會把磁盤塊1由磁盤加載到內存组哩，此時發(fā)生一次IO，在內存中用二分查找確定29在17和35之間处渣，鎖定磁盤塊1的P2指針伶贰，內存時間因為非常短（相比磁盤的IO）可以忽略不計，通過磁盤塊1的P2指針的磁盤地址把磁盤塊3由磁盤加載到內存罐栈，發(fā)生第二次IO黍衙，29在26和30之間，鎖定磁盤塊3的P2指針荠诬，通過指針加載磁盤塊8到內存们豌，發(fā)生第三次IO，同時內存中做二分查找找到29浅妆，結束查詢望迎，總計三次IO。真實的情況是凌外，3層的b+樹可以表示上百萬的數據辩尊，如果上百萬的數據查找只需要三次IO，性能提高將是巨大的康辑，如果沒有索引摄欲，每個數據項都要發(fā)生一次IO轿亮，那么總共需要百萬次的IO，顯然成本非常非常高胸墙。
b+樹性質
1.通過上面的分析我注，我們知道IO次數取決于b+數的高度h，假設當前數據表的數據為N迟隅，每個磁盤塊的數據項的數量是m但骨，則有h=㏒(m+1)N，當數據量N一定的情況下智袭，m越大奔缠，h越小吼野；而m = 磁盤塊的大小 / 數據項的大小校哎，磁盤塊的大小也就是一個數據頁的大小，是固定的瞳步，如果數據項占的空間越小闷哆，數據項的數量越多，樹的高度越低单起。這就是為什么每個數據項阳准，即索引字段要盡量的小，比如int占4字節(jié)馏臭，要比bigint8字節(jié)少一半。這也是為什么b+樹要求把真實的數據放到葉子節(jié)點而不是內層節(jié)點讼稚，一旦放到內層節(jié)點括儒，磁盤塊的數據項會大幅度下降，導致樹增高锐想。當數據項等于1時將會退化成線性表帮寻。
2.當b+樹的數據項是復合的數據結構，比如(name,age,sex)的時候赠摇，b+數是按照從左到右的順序來建立搜索樹的固逗，比如當(張三,20,F)這樣的數據來檢索的時候，b+樹會優(yōu)先比較name來確定下一步的所搜方向藕帜，如果name相同再依次比較age和sex烫罩，最后得到檢索的數據；但當(20,F)這樣的沒有name的數據來的時候洽故，b+樹就不知道下一步該查哪個節(jié)點贝攒，因為建立搜索樹的時候name就是第一個比較因子，必須要先根據name來搜索才能知道下一步去哪里查詢时甚。比如當(張三,F)這樣的數據來檢索時隘弊，b+樹可以用name來指定搜索方向哈踱，但下一個字段age的缺失，所以只能把名字等于張三的數據都找到梨熙，然后再匹配性別是F的數據了开镣， 這個是非常重要的性質，即索引的最左匹配特性咽扇。
