前言
面試中我們經常碰到面試官問到資料庫索引，問到索引就會問你索引的資料結構。類似這種資料結構對于普通程式員來說記住概念幾天就忘了，而且概念不是每個人都能很好都了解，是以針對這一原因，我簡單通俗都像大家講解為什麼mysql使用都是B+樹，而不用其他的樹形結構。
正文
Q1：B+樹的查詢時間大概多少？
A：跟樹的高度有關，是O(log n)。
Q2：hash查找時間大概多少？
A：o（1）。
Q3：hash比B+查找時間更短，為什麼索引不用hash？
A：這和業務場景有關，如果隻查找一個值的話，hash是一個很好的選擇，單資料庫經常會選擇多條，這時候由于B+樹索引有序，并且又有連結清單相連，它的查詢效率比hash就快很多了。而且資料庫中的索引一般是在磁盤上，資料量大的情況可能無法一次裝入記憶體，B+樹的設計可以允許資料分批加載，同時樹的高度較低，提高查找效率。
下面我對第三個問題進行一個解析，讓大家更好的記住。
二叉排序樹
同一高度下左邊跟節點小，右邊跟節點大，并且左右子樹都是二叉排序的。但是在極端情況下插入的是有序的序列就會變成連結清單。
是以這時候我們就要對二叉樹進行平衡，讓插入的時候節點能均勻分布。
紅黑樹
- 性質1. 節點是紅色或黑色。
- 性質2. 根節點是黑色。
- 性質3 每個葉節點（NIL節點，空節點）是黑色的。
- 性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
- 性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
是以引入紅黑樹，紅黑樹是平衡樹的一種，他的複雜規則都是為了保證樹的平衡，是以大家在記概念的時候了解不上去。
我們知道，樹形結構的資料查找速度跟樹的高度有關，是以盡可能讓樹平衡就是為了降低樹的高度，java裡有一種s資料結構底層就用的紅黑樹，就是TreeSet。
B樹，也叫B-樹，大家千萬不要說B減樹。
B樹是一種多路搜尋樹，每個節點都可以有多于兩個子節點，M路的B樹就是有最多有M個子節點。
這就是一個3路B樹
多路的結構就是為了盡可能降低樹的高度，使查詢速度更快，有一種情況就是無限多路，那就變成一個數組了，是以我們樹ArrayList适合用來查詢，數組結構的資料都有這個特點。
是以我們常常用B樹做檔案系統的索引，因為我們檔案和資料庫的索引都是存在硬碟上的，并且如果資料量大的話，不一定能一次性加載到記憶體中。是以一棵樹無法全部加載到記憶體裡我們怎麼查找，這時候就用到我們剛才說到的B樹了，我們可以每次加載樹的每一個節點，然後一步一步往下查找，而且多路B樹每個節點會多于兩個子節點，速度會更快，是以我們不用紅黑樹，因為紅黑樹子節點隻有兩個。
B+樹
B+樹是在B樹基礎上改造的，他的資料都在葉子節點，同時葉子節點還加了指針。
這是一個四路B+樹，葉子節點都資料形成了連結清單
這也是和業務場景相關的，你想想，資料庫中select資料，不一定隻選一條，很多時候會選多條，比如按照id排序後選10條。如果是多條的話，B樹需要做局部的中序周遊，可能要跨層通路。而B+樹由于所有資料都在葉子結點，不用跨層，同時由于有連結清單結構，隻需要找到首尾，通過連結清單就能把所有資料取出來了。
比如我們查找7到19，B+ 都威力看到了吧。是以小夥伴們回到前文都三個問題中，就知道了為什麼MySql索引使用B+樹了吧。
如果喜歡請關注公衆号，更多精彩内容