https://www.cnblogs.com/aspirant/p/9214485.html
一步步分析為什么B+樹適合作為索引的結構 以及索引原理
mysql的B+樹索引 查找使用了二分查找，redis 跳表也使用了二分查找法，kafka查詢訊息日志也使用了二分查找法，二分查找法時間復雜度O(logn);
參考：redis的索引底層的 跳表原理 實作 聊聊Mysql索引和redis跳表 ---redis的跳表原理 時間復雜度O(logn)(阿里)
參考：kafka如何實作高并發存盤-如何找到一條需要消費的資料(阿里)
參考：二分查找法：各種排序演算法的時間復雜度和空間復雜度(阿里)
在MySQL中，主要有四種型別的索引，分別為：B-Tree索引，Hash索引，Fulltext索引(MyISAM 表)和R-Tree索引，本文講的是B-Tree索引，
后面的索引原理一定要看，太重要了，阿里兩個人都問這個mysql的索引原理
mysql使用了 B+索引：
B樹：有序陣列+平衡多叉樹；
B+樹：有序陣列鏈表+平衡多叉樹；
一、Mysql索引主要有兩種結構：B+Tree索引和Hash索引
(a) Inodb存盤引擎 默認是 B+Tree索引
(b) MyISAM 存盤引擎 默認是Fulltext索引；
(c)Memory 存盤引擎 默認 Hash索引；
Hash索引
mysql中，只有Memory(Memory表只存在記憶體中，斷電會消失，適用于臨時表)存盤引擎顯示支持Hash索引，是Memory表的默認索引型別，盡管Memory表也可以使用B+Tree索引，Hash索引把資料以hash形式組織起來，因此當查找某一條記錄的時候，速度非常快，但是因為hash結構，每個鍵只對應一個值，而且是散列的方式分布，所以它并不支持范圍查找和排序等功能，
B+Tree索引
B+Tree是mysql使用最頻繁的一個索引資料結構，是Inodb和Myisam存盤引擎模式的索引型別，相對Hash索引，B+Tree在查找單條記錄的速度比不上Hash索引，但是因為更適合排序等操作，所以它更受歡迎，畢竟不可能只對資料庫進行單條記錄的操作，
帶順序訪問指標的B+Tree
B+Tree所有索引資料都在葉子節點上，并且增加了順序訪問指標，每個葉子節點都有指向相鄰葉子節點的指標，
這樣做是為了提高區間效率，例如查詢key為從18到49的所有資料記錄，當找到18后，只要順著節點和指標順序遍歷就可以以此向訪問到所有資料節點，極大提高了區間查詢效率，
大大減少磁盤I/O讀取
資料庫系統的設計者巧妙利用了磁盤預讀原理，將一個節點的大小設為等于一個頁，這樣每個節點需要一次I/O就可以完全載入，
什么是索引
索引（Index）是幫助資料庫高效獲取資料的資料結構，索引是在基于資料庫表創建的，它包含一個表中某些列的值以及記錄對應的地址，并且把這些值存盤在一個資料結構中，最常見的就是使用哈希表、B+樹作為索引，
一般的應用系統，讀寫比例在10:1左右，而且插入操作和一般的更新操作很少出現性能問題，在生產環境中，我們遇到最多的，也是最容易出問題的，還是一些復雜的查詢操作，因此對查詢陳述句的優化顯然是重中之重，說起加速查詢，就不得不提到索引了，
為什么要使用索引
我們知道，資料庫查詢是資料庫最主要的功能之一，而查詢速度當然是越快越好，而當資料量越來越大的時候，查詢花費的時間會隨之增長，而索引，可以加速資料的查詢，因為索引是有序排列的，
舉個例子來說，假設我們有一個資料庫表Employee，這個表分別有三個欄位：name，age，address，假設表中有1000條記錄，
假如沒有使用索引，當我們查詢名為“Jesus”的雇員的時候，即呼叫：
select name,age,address from Employee where name = 'Jesus';
此時資料庫不得不在Employee表中對這1000條記錄一條一條的進行判斷name欄位是否為“Jesus”，這也就是所謂的全表掃描，
而當我們在Employee表上的name欄位上創建索引時，當我們查詢名為“Jesus”的雇員時，會通過索引查找去查詢名為“Jesus”的雇員，因為該索引已經按照字母順序排列，因此要查找名為“Jesus”的記錄時會快很多，因為名字首字母為“J”的雇員都是排列在一起的，通過該索引，能獲取到表中對應的記錄，
舉例說明使用索引的好處
假設索引（索引是一種資料結構）是鏈表結構，每個節點存盤的是關鍵字欄位（這個例子中對應的是name屬性）以及該關鍵字欄位在資料庫表的對應的記錄的地址，而這些節點是根據name屬性排序的（即根據字母順序排序），因此，當我們執行上面說的查找名為“Jesus”的sql陳述句時，資料庫會通過該索引來查詢，因為該鏈表是有序排列的，在我們找到第一個name屬性為“Jesus”的節點后，繼續往后找，當遇到name屬性不為“Jesus”的節點時，就無需再往后查找了，因為節點是根據name屬性有序排列的啊，假設第一個name=“Jesus”的節點是第499個節點，最后一個name=“Jesus”的節點是第500個節點，那么只需要遍歷501個節點就可以了，當發現第501個節點的name欄位不為“Jesus”，后面的499個節點也就無需遍歷了，通過索引，我們就找到了name為“Jesus”的節點，而通過該節點的另一個屬性（關鍵字欄位在資料庫表的對應的記錄的地址），我們就能獲取到Employee表中滿足條件name=“Jesus”的記錄了，
通過使用索引，查詢判斷的次數就從1000次縮小到了501次了，起到了加速了查詢效率，但實際上資料庫中索引的結構，并不是鏈表結構，
資料庫中使用什么資料結構作為索引
資料庫中實際使用的索引并不會是鏈表結構，因為效率太低了，
我們知道鏈表的查詢效率是O(n)，就像上面的例子，遍歷了501次才找到第一條符合條件的記錄，這是很低效的，而我們知道，陣列+二分查找的效率是O(lgn)，但是陣列的插入元素以及洗掉元素的效率很低，因此使用陣列做為索引結構并不合適，
另外，在選擇資料庫索引的結構的時候，要考慮到另一個問題，索引是存在于磁盤中，當索引非常大的時候，達到幾個G的時候，無法一次加載到記憶體中，
考慮到上面兩個因素，資料庫中索引使用的是樹形結構，
各種樹的名字
有這么幾種樹：
B-Tree B+-Tree B*-Tree
首先要明白三種樹名中的“-”起到的是分隔的作用，并不是“減”的意思，
因此正確的翻譯應該是B樹，B+樹，B*樹，而不是B-樹，B+樹，B*樹，因此，當你聽到別人說“B減樹”的時候，要明白它指的是B-Tree，即B樹和B-樹是同一種樹，
為什么要強調上面這一點呢，因為有的博文中寫的是：B樹是二叉樹，B-樹是多路搜索樹，
然而B樹和B-樹都是指B-Tree，參考維基百科上的話：
B-tree Not to be confused with Binary tree.
也就是說，B-Tree并不是Binart tree，B-Tree的中文名是平衡多路搜索樹，
（B樹的相關介紹在下面）
平衡二叉樹
樹形結構是計算機系統里最重要的資料結構，
我們知道，二叉樹的查找的時間復雜度是O(log2N)，其查找效率與深度有關，而普通的二叉樹可能由于內部節點排列問題退化成鏈表，這樣查找效率就會很低，因此平衡二叉樹是更好的選擇，因為它保持平衡，即通過旋轉調整結構保持最小的深度，其查找的時間復雜度也是O(log2N)，
但實際上，資料庫中索引的結構也并非AVL樹或更優秀的紅黑樹，盡管它的查詢的時間復雜度很低，
為什么平衡二叉樹也不適合作為索引
之前說了平衡樹的查找時間復雜度是O(log2N)，已經很不錯了，但還是不適合作為索引結構，那么肯定是有一種更適合作為索引的資料結構，那么這個更適合作為索引的資料結構，難道是查找的時間復雜度更低嗎？并不是，這種作為索引的資料結構的查找的時間復雜度也近似O(log2N)，
那為什么平衡二叉樹不適合作為索引呢？
索引是存在于索引檔案中，是存在于磁盤中的，因為索引通常是很大的，因此無法一次將全部索引加載到記憶體當中，因此每次只能從磁盤中讀取一個磁盤頁的資料到記憶體中，而這個磁盤的讀取的速度較記憶體中的讀取速度而言是差了好幾個級別，
注意，我們說的平衡二叉樹結構，指的是邏輯結構上的平衡二叉樹，其物理實作是陣列，然后由于在邏輯結構上相近的節點在物理結構上可能會差很遠，因此，每次讀取的磁盤頁的資料中有許多是用不上的，因此，查找程序中要進行許多次的磁盤讀取操作，
而適合作為索引的結構應該是盡可能少的執行磁盤IO操作，因為執行磁盤IO操作非常的耗時，因此，平衡二叉樹并不適合作為索引結構，
B-Tree適合作為索引
平衡二叉樹不適合作為索引，那么什么才適合作為索引——B樹，
平衡二叉樹沒能充分利用磁盤預讀功能，而B樹是為了充分利用磁盤預讀功能來而創建的一種資料結構，也就是說B樹就是為了作為索引才被發明出來的的，
來看看關于“區域性原理與磁盤預讀”的知識：
區域性原理與磁盤預讀： 由于存盤介質的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O，為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個位元組，磁盤也會從這個位置開始，順序向后讀取一定長度的資料放入記憶體，這樣做的理論依據是計算機科學中著名的區域性原理： 當一個資料被用到時，其附近的資料也通常會馬上被使用， 程式運行期間所需要的資料通常比較集中， 由于磁盤順序讀取的效率很高（不需要尋道時間，只需很少的旋轉時間），因此對于具有區域性的程式來說，預讀可以提高I/O效率，
搞清楚上面的意思，磁盤預讀是具體實作，其理論依據是區域性原理，
為什么說紅黑樹沒能充分利用磁盤預讀功能，參考一篇博文的一段話：
紅黑樹這種結構，h明顯要深的多，由于邏輯上很近的節點（父子）物理上可能很遠，無法利用區域性，所以紅黑樹的I/O漸進復雜度也為O(h)，效率明顯比B-Tree差很多，
也就是說，使用紅黑樹（平衡二叉樹）結構的話，每次磁盤預讀中的很多資料是用不上的資料，因此，它沒能利用好磁盤預讀的提供的資料，然后又由于深度大（較B樹而言），所以進行的磁盤IO操作更多，
B樹的每個節點可以存盤多個關鍵字，它將節點大小設定為磁盤頁的大小，充分利用了磁盤預讀的功能，每次讀取磁盤頁時就會讀取一整個節點，也正因每個節點存盤著非常多個關鍵字，樹的深度就會非常的小，進而要執行的磁盤讀取操作次數就會非常少，更多的是在記憶體中對讀取進來的資料進行查找，
B樹的查詢，主要發生在記憶體中，而平衡二叉樹的查詢，則是發生在磁盤讀取中，因此，雖然B樹查詢查詢的次數不比平衡二叉樹的次數少，但是相比起磁盤IO速度，記憶體中比較的耗時就可以忽略不計了，因此，B樹更適合作為索引，
比B樹更適合作為索引的結構——B+樹
比B樹更適合作為索引的結構是B+樹，MySQL中也是使用B+樹作為索引，它是B樹的變種，因此是基于B樹來改進的，為什么B+樹會比B樹更加優秀呢？
B樹：有序陣列+平衡多叉樹；
B+樹：有序陣列鏈表+平衡多叉樹；
B+樹的關鍵字全部存放在葉子節點中，非葉子節點用來做索引，而葉子節點中有一個指標指向一下個葉子節點，做這個優化的目的是為了提高區間訪問的性能，而正是這個特性決定了B+樹更適合用來存盤外部資料，
參考一段話：
走進搜索引擎的作者梁斌老師針對B樹、B+樹給出了他的意見（為了真實性，特參考其原話，未作任何改動）： “B+樹還有一個最大的好處，方便掃庫，B樹必須用中序遍歷的方法按序掃庫，而B+樹直接從葉子結點挨個掃一遍就完了，B+樹支持range-query非常方便，而B樹不支持，這是資料庫選用B+樹的最主要原因， 比如要查 5-10之間的，B+樹一把到5這個標記，再一把到10，然后串起來就行了，B樹就非常麻煩，B樹的好處，就是成功查詢特別有利，因為樹的高度總體要比B+樹矮，不成功的情況下，B樹也比B+樹稍稍占一點點便宜， B樹比如你的例子中查，17的話，一把就得到結果了， 有很多基于頻率的搜索是選用B樹，越頻繁query的結點越往根上走，前提是需要對query做統計，而且要對key做一些變化， 另外B樹也好B+樹也好，根或者上面幾層因為被反復query，所以這幾塊基本都在記憶體中，不會出現讀磁盤IO，一般已啟動的時候，就會主動換入記憶體，”
舉個例子來對比，
B樹：
比如說，我們要查找關鍵字范圍在3到7的關鍵字，在找到第一個符合條件的數字3后，訪問完第一個關鍵字所在的塊后，得遍歷這個B樹，獲取下一個塊，直到遇到一個不符合條件的關鍵字，遍歷的程序是比較復雜的，
B+樹(葉節點保存資料，其他的節點 全部存放索引)： 
相比之下，B+樹的基于范圍的查詢簡潔很多，由于葉子節點有指向下一個葉子節點的指標，因此從塊1到塊2的訪問，通過塊1指向塊2的指標即可，從塊2到塊3也是通過一個指標即可，
參考一篇博文中網友評論的一段話：
資料庫索引采用B+樹的主要原因是B樹在提高了磁盤IO性能的同時并沒有解決元素遍歷的效率低下的問題，正是為了解決這個問題，B+樹應運而生，
B+樹只要遍歷葉子節點就可以實作整棵樹的遍歷，而且在資料庫中基于范圍的查詢是非常頻繁的，而B樹不支持這樣的操作（或者說效率太低），
正如上面所說，在資料庫中基于范圍的查詢是非常頻繁的，因此MySQL最終選擇的索引結構是B+樹而不是B樹，
二、索引的原理
一 索引原理
索引的目的在于提高查詢效率，與我們查閱圖書所用的目錄是一個道理：先定位到章，然后定位到該章下的一個小節，然后找到頁數，相似的例子還有：查字典，查火車車次，飛機航班等
本質都是：通過不斷地縮小想要獲取資料的范圍來篩選出最終想要的結果，同時把隨機的事件變成順序的事件，也就是說，有了這種索引機制，我們可以總是用同一種查找方式來鎖定資料，
資料庫也是一樣，但顯然要復雜的多，因為不僅面臨著等值查詢，還有范圍查詢(>、<、between、in)、模糊查詢(like)、并集查詢(or)等等，資料庫應該選擇怎么樣的方式來應對所有的問題呢？我們回想字典的例子，能不能把資料分成段，然后分段查詢呢？最簡單的如果1000條資料，1到100分成第一段，101到200分成第二段，201到300分成第三段......這樣查第250條資料，只要找第三段就可以了，一下子去除了90%的無效資料，但如果是1千萬的記錄呢，分成幾段比較好？稍有演算法基礎的同學會想到搜索樹，其平均復雜度是lgN，具有不錯的查詢性能，但這里我們忽略了一個關鍵的問題，復雜度模型是基于每次相同的操作成本來考慮的，而資料庫實作比較復雜，一方面資料是保存在磁盤上的，另外一方面為了提高性能，每次又可以把部分資料讀入記憶體來計算，因為我們知道訪問磁盤的成本大概是訪問記憶體的十萬倍左右，所以簡單的搜索樹難以滿足復雜的應用場景，
二 磁盤IO與預讀
考慮到磁盤IO是非常高昂的操作，計算機作業系統做了一些優化，當一次IO時，不光把當前磁盤地址的資料，而是把相鄰的資料也都讀取到記憶體緩沖區內，因為區域預讀性原理告訴我們，當計算機訪問一個地址的資料的時候，與其相鄰的資料也會很快被訪問到，每一次IO讀取的資料我們稱之為一頁(page)，具體一頁有多大資料跟作業系統有關，一般為4k或8k，也就是我們讀取一頁內的資料時候，實際上才發生了一次IO，這個理論對于索引的資料結構設計非常有幫助，
三、索引的資料結構
任何一種資料結構都不是憑空產生的，一定會有它的背景和使用場景，我們現在總結一下，我們需要這種資料結構能夠做些什么，其實很簡單，那就是：每次查找資料時把磁盤IO次數控制在一個很小的數量級，最好是常數數量級，那么我們就想到如果一個高度可控的多路搜索樹是否能滿足需求呢？就這樣，b+樹應運而生，
如上圖，是一顆b+樹，關于b+樹的定義可以參見B+樹，這里只說一些重點，淺藍色的塊我們稱之為一個磁盤塊，可以看到每個磁盤塊包含幾個資料項（深藍色所示）和指標（黃色所示），如磁盤塊1包含資料項17和35，包含指標P1、P2、P3，P1表示小于17的磁盤塊，P2表示在17和35之間的磁盤塊，P3表示大于35的磁盤塊，真實的資料存在于葉子節點即3、5、9、10、13、15、28、29、36、60、75、79、90、99，非葉子節點只不存盤真實的資料，只存盤指引搜索方向的資料項，如17、35并不真實存在于資料表中，
###b+樹的查找程序
如圖所示，如果要查找資料項29，那么首先會把磁盤塊1由磁盤加載到記憶體，此時發生一次IO，在記憶體中用二分查找確定29在17和35之間，鎖定磁盤塊1的P2指標，記憶體時間因為非常短（相比磁盤的IO）可以忽略不計，通過磁盤塊1的P2指標的磁盤地址把磁盤塊3由磁盤加載到記憶體，發生第二次IO，29在26和30之間，鎖定磁盤塊3的P2指標，通過指標加載磁盤塊8到記憶體，發生第三次IO，同時記憶體中做二分查找找到29，結束查詢，總計三次IO，真實的情況是，3層的b+樹可以表示上百萬的資料，如果上百萬的資料查找只需要三次IO，性能提高將是巨大的，如果沒有索引，每個資料項都要發生一次IO，那么總共需要百萬次的IO，顯然成本非常非常高，
###b+樹性質
1.索引欄位要盡量的小：通過上面的分析，我們知道IO次數取決于b+數的高度h，假設當前資料表的資料為N，每個磁盤塊的資料項的數量是m，則有h=㏒(m+1)N，當資料量N一定的情況下，m越大，h越小；而m = 磁盤塊的大小 / 資料項的大小，磁盤塊的大小也就是一個資料頁的大小，是固定的，如果資料項占的空間越小，資料項的數量越多，樹的高度越低，這就是為什么每個資料項，即索引欄位要盡量的小，比如int占4位元組，要比bigint8位元組少一半，這也是為什么b+樹要求把真實的資料放到葉子節點而不是內層節點，一旦放到內層節點，磁盤塊的資料項會大幅度下降，導致樹增高，當資料項等于1時將會退化成線性表，
2.索引的最左匹配特性（即從左往右匹配）：當b+樹的資料項是復合的資料結構，比如(name,age,sex)的時候，b+數是按照從左到右的順序來建立搜索樹的，比如當(張三,20,F)這樣的資料來檢索的時候，b+樹會優先比較name來確定下一步的所搜方向，如果name相同再依次比較age和sex，最后得到檢索的資料；但當(20,F)這樣的沒有name的資料來的時候，b+樹就不知道下一步該查哪個節點，因為建立搜索樹的時候name就是第一個比較因子，必須要先根據name來搜索才能知道下一步去哪里查詢，比如當(張三,F)這樣的資料來檢索時，b+樹可以用name來指定搜索方向，但下一個欄位age的缺失，所以只能把名字等于張三的資料都找到，然后再匹配性別是F的資料了， 這個是非常重要的性質，即索引的最左匹配特性，
這也是經常考察的，比如 我定義了 A,B,C的聯合索引，如果 我只傳遞了 A,B 能走索引嗎？答案是能，因為最左側原理(百度問過)
補充一下. 全文索引（FULLTEXT）=mysql的 myISAM搜索引擎默認的索引型別
MySQL從3.23.23版開始支持全文索引和全文檢索，fulltext索引僅可用于 MyISAM 表；他們可以從CHAR、VARCHAR或TEXT列中作為CREATE TABLE陳述句的一部分被創建，或是隨后使用ALTER TABLE 或CREATE INDEX被添加，////對于較大的資料集，將你的資料輸入一個沒有FULLTEXT索引的表中，然后創建索引，其速度比把資料輸入現有FULLTEXT索引的速度更為快，不過切記對于大容量的資料表，生成全文索引是一個非常消耗時間非常消耗硬碟空間的做法，
文本欄位上的普通索引只能加快對出現在欄位內容最前面的字串(也就是欄位內容開頭的字符)進行檢索操作，如果欄位里存放的是由幾個、甚至是多個單詞構成的較大段文字，普通索引就沒什么作用了，這種檢索往往以LIKE %word%的形式出現，這對MySQL來說很復雜，如果需要處理的資料量很大，回應時間就會很長，
這類場合正是全文索引(full-text index)可以大顯身手的地方，在生成這種型別的索引時，MySQL將把在文本中出現的所有單詞創建為一份清單，查詢操作將根據這份清單去檢索有關的資料記錄，全文索引即可以隨資料表一同創建，也可以等日后有必要時再使用下面這條命令添加：
ALTER TABLE table_name ADD FULLTEXT(column1, column2)
有了全文索引，就可以用SELECT查詢命令去檢索那些包含著一個或多個給定單詞的資料記錄了，下面是這類查詢命令的基本語法：
SELECT * FROM table_name
WHERE MATCH(column1, column2) AGAINST('word1', 'word2', 'word3')
上面這條命令將把column1和column2欄位里有word1、word2和word3的資料記錄全部查詢出來，
參考：Mysql索引詳解及優化(key和index區別)
四，索引使用注意事項
1，不要濫用索引
①，索引提高查詢速度，卻會降低更新表的速度，因為更新表時，mysql不僅要更新資料，保存資料，還要更新索引，保存索引
②，索引會占用磁盤空間
2，索引不會包含含有NULL值的列
復合索引只要有一列含有NULL值,那么這一列對于此符合索引就是無效的，因此我們在設計資料庫設計時不要讓欄位的默認值為NULL，
3，MySQL查詢只是用一個索引
如果where字句中使用了索引的話，那么order by中的列是不會使用索引的
4，like
like '%aaa%'不會使用索引而like "aaa%"可以使用索引
二、選擇索引的資料型別
Mysql支持很多資料型別，選擇合適的資料型別存盤資料對性能有很大的影響，
(1)越小的資料型別通常更好：越小的資料型別通常在磁盤、記憶體和cpu快取中都需要更少的空間，處理起來更快，
(2)簡單的資料型別更好：整形資料比起字符，處理開銷更小，因為字串的比較更復雜，在MySQL中，應用內置的日期和時間資料型別，而不是字串來存盤時間；以及用整形資料存盤IP地址，
(3)盡量避免NULL：應該制定列為NOT NULL，除非你想存盤NULL，在MySQL中，含有空值的列很難進行查詢優化，因為他們使得索引、索引的統計資訊以及比較運算更加復雜，
三、MySQL常見索引有：主鍵索引、唯一索引、普通索引、全文索引、組合索引
1，INDEX（普通索引）：ALTER TABLE 'table_name' ADD INDEX index_name('col')
最基本的索引，沒有任何限制
2，UNIQUE（唯一索引）：ALTER TABLE 'table_name' ADD UNIQUE('col')
與“普通索引”類似，不同的就是：索引列的值必須唯一，但允許有空值，
3，PRIMARY KEY（主鍵索引）：ALTER TABLE 'table_name' ADD PRIMARY KEY('col')
是一種特殊的唯一索引，不允許有空值，
4，FULLTEXT（全文索引）：ALTER TABLE 'table_name' ADD FULLTEXT('col')
僅可用于MyISAM和InoDB，針對較大的資料，生成全文索引很耗時耗空間
組合索引：ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3')
為了更多的提高mysql效率可建立組合索引，遵循“最左前綴”原則，創建復合索引應該將最常用（頻率）做限制條件的列放在最左邊，一次遞減，組合索引最左欄位用in是可以用到索引的，相當于建立了col1,col1col2,col1col2col3三個索引
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/42262.html
標籤：MySQL