目錄
- 二叉查找樹為索引
- 紅黑樹為索引
- B樹作為索引
- B+樹作為索引
- MyISAM存儲引擎索引實現
- InnoDB存儲引擎索引實現
- 常見問題
- 聚集索引與非聚集索引
- InnoDB基于主鍵索引和普通索引的查詢有什么區別？
- InnoDB主鍵索引為何是整型的自增主鍵
- 何時使用業務字段作為主鍵呢？
- 哈希與B樹
- “N叉樹”的N值在MySQL中是可以被人工調整的么？
二叉查找樹為索引
二叉樹的key為col2，value為索引所在行的磁盤地址。
但如果拿col1來作為key的話，會發現二叉搜索樹退化成鏈表。
紅黑樹為索引
仍然以col1作為索引key，發現找6只需要查找3次。比二叉查找樹更加合適一點
當表中有1百萬行數據時，這棵樹的高度會越來越大。如果我們查找的元素在葉子節點，查找次數會非常多。
B樹作為索引
可以在樹的橫向上做文章，每個節點原本只存儲一行數據的地址，現在可以修改為存儲多行數據。因為樹的高度越多說明IO操作越多，導致與磁盤的交互越多。
B樹：
葉節點具有相同的深度，葉節點的指針為空。
所有的索引元素不重復
節點中數據索引從左到右遞增排列
B+樹作為索引
B+樹
非葉子節點不存儲data，只存儲索引，這樣可以放更多索引
葉子節點包含所有索引字段。
葉子節點用指針連接，提高區間訪問性能。
也就是說在葉子節點存儲了完整的元素，然后把一些處于中間位置的索引元素提取出來，作為非葉子節點。
MySQL設置默認節點大小為16kb，一個bigint為8byte，一個指針為6byte。所以一個節點最多能存16kb/14b = 1170。
再假設葉子節點一個元素占空間大小為1kb。
如果全部節點存儲了滿了，h = 3的時候一共能夠存儲1170 * 1170 * 16 = 21902400；這樣可以存兩千多萬個數據了。
以下面為例：
注意，整個樹都放在磁盤中，每次load一個節點進入內存。一般來說，先從根節點開始load。
我們現在要找6。比對根節點的3，6大于3，向右比較，發現6大于5，于是從5右邊的指針找到下面一層的節點.
然后把這一層的節點從磁盤里面load到內存中。
我們還可以看到最底層的節點之間會有鏈表相連。
MyISAM存儲引擎索引實現
注意，存儲引擎是用來形容數據庫中的表的。
MyISAM索引文件和數據文件是分離的。
我們使用查詢語句：
select * from ... where Col1 = 49;
首先查找是否是索引字段，如果是就從MYI文件中的B+樹里面去定位到這個元素。key存儲的是索引元素，data存儲的是索引元素所在的那一行的磁盤地址指針。拿到指針后去MYD文件定位。
InnoDB存儲引擎索引實現
索引和數據放到了同一個文件中：.ibd文件。
葉節點包含了完整的數據記錄，而不只是一個地址指針。
常見問題
聚集索引與非聚集索引
InnoDB就是聚集索引，索引和數據文件合在一起。
MyISAM是非聚集索引，索引和數據文件分離。
非聚集索引要查找兩次，一次找到指針地址，一次根據指針地址找具體數據。
聚集索引只需要查找一次，直接找到具體數據，所以效率要更高。
InnoDB基于主鍵索引和普通索引的查詢有什么區別？
如果語句是 select * from T where ID=500，即主鍵查詢方式，則只需要搜索 ID 這棵 B+ 樹；
如果語句是 select * from T where k=5，即普通索引查詢方式，則需要先搜索 k 索引樹，得到 ID 的值為 500，再到 ID 索引樹搜索一次。這個過程稱為回表。
也就是說，基于非主鍵索引的查詢需要多掃描一棵索引樹。因此，我們在應用中應該盡量使用主鍵查詢。
InnoDB主鍵索引為何是整型的自增主鍵
自增主鍵的使用，關于存儲和性能
InnoDB必須要有主鍵，而且推薦使用的是整型的自增主鍵。
因為數字好建立索引，方便比較，而且相比較于字符串類型，占用的空間更小。
關于自增：由于底層葉子節點是遞增排列的，如果此時主鍵是遞增的，那么新插入的元素就顯然在葉子節點的最右邊。
如果主鍵不是遞增的，插入一個新的元素可能就會在葉子節點鏈表中間某處。B+樹的結構調整就十分巨大了，可能上層的非葉子節點的索引值要修改。
例如這里我們插入8
樹的結構發生了很大變化，直接裂開。
自增主鍵的插入數據模式，每次插入一條新記錄，都是追加操作，都不涉及到挪動其他記錄，也不會觸發葉子節點的分裂。
何時使用業務字段作為主鍵呢？
只有唯一的索引，而且該索引為唯一索引。由于沒有其他索引，所以也就不用考慮其他索引的葉子節點大小的問題。
直接將這個索引設置為主鍵，可以避免每次查詢需要搜索兩棵樹。
哈希與B樹
哈希查找某個key很快，但是不支持范圍查找。
B樹用到范圍查找就很方便了。葉子節點從左到右是一個遞增的趨勢。并且葉子節點之間通過指針相連，所以不需要再返回到上層索引中尋找。如果我們要找大于20的元素，那么只要在最底層，20元素的右邊進行遍歷即可。
如果是小于某個元素的情況，就是從底層葉子節點的左邊開始，一直包含到邊界即可。
“N叉樹”的N值在MySQL中是可以被人工調整的么？
1， 通過改變key值來調整
N叉樹中非葉子節點存放的是索引信息，索引包含Key和Point指針。Point指針固定為6個字節，假如Key為10個字節，那么單個索引就是16個字節。如果B+樹中頁大小為16K，那么一個頁就可以存儲1024個索引，此時N就等于1024。我們通過改變Key的大小，就可以改變N的值
2， 改變頁的大小
頁越大，一頁存放的索引就越多，N就越大。
數據頁調整后，如果數據頁太小層數會太深，數據頁太大，加載到內存的時間和單個數據頁查詢時間會提高，需要達到平衡才行。
