什么是聚集索引烹玉，非聚集索引药蜻，索引覆蓋御毅，回表轧抗，索引下推
如何理解Mysql的索引及他們的原理抡锈？
為什么mysql用B+樹(shù)做索引而不用B-樹(shù)或紅黑樹(shù)
數(shù)據(jù)庫(kù)索引（B樹(shù)疾忍，B+樹(shù)，哈希）
二叉樹(shù)
對(duì)于查找床三，我們很容易想到二叉查找樹(shù)一罩，但是二叉查找樹(shù)查找效率不穩(wěn)定，時(shí)間可能在O(logn) - O(n),O(n)為二叉查找樹(shù)為鏈表的時(shí)候
平衡二叉查找樹(shù)
平衡二叉查找樹(shù)滿足撇簿，左子樹(shù)的值都小于根節(jié)點(diǎn)的值聂渊，右子樹(shù)的值都大于根節(jié)點(diǎn)的值。且左右子樹(shù)的高度差不大于1四瘫。這樣查找的復(fù)雜度就是O(logn)汉嗽，但是二叉查找樹(shù)的一個(gè)節(jié)點(diǎn)只有左右兩個(gè)子節(jié)點(diǎn)，如果數(shù)據(jù)量多找蜜，會(huì)造成樹(shù)的高度非常龐大
B樹(shù)
B樹(shù)可以有不止兩個(gè)子節(jié)點(diǎn)饼暑，B樹(shù)一個(gè)節(jié)點(diǎn)包含了子節(jié)點(diǎn)的磁盤(pán)地址，主鍵的值，還有行數(shù)據(jù)撵孤。
B樹(shù)有兩個(gè)不好的地方
- 查詢(xún)效率不穩(wěn)定
- B樹(shù)每個(gè)節(jié)點(diǎn)都有data迈着，因?yàn)楣?jié)點(diǎn)都是存在磁盤(pán)里的，每次從磁盤(pán)里只能一頁(yè)一頁(yè)地讀邪码，B樹(shù)多了個(gè)data指針裕菠，無(wú)疑會(huì)加大磁盤(pán)的消耗，讀一次數(shù)據(jù)就減少讀到節(jié)點(diǎn)的數(shù)目 (（磁盤(pán)IO一次讀出的數(shù)據(jù)量大小是固定的闭专，單個(gè)數(shù)據(jù)變大奴潘，每次讀出的就少，IO次數(shù)增多影钉，一次IO多耗時(shí)）)
- B樹(shù)做范圍查詢(xún)比較難
B+樹(shù)
B+樹(shù)相對(duì)于B樹(shù)有幾點(diǎn)不同：
- 非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值和指針画髓。
- 所有葉子節(jié)點(diǎn)之間都有一個(gè)鏈指針。
- 數(shù)據(jù)記錄都存放在葉子節(jié)點(diǎn)中平委。
B+樹(shù)相對(duì)B樹(shù)的優(yōu)點(diǎn)
- B+樹(shù)只有葉節(jié)點(diǎn)存放數(shù)據(jù)奈虾，其余節(jié)點(diǎn)用來(lái)索引，而B(niǎo)-樹(shù)是每個(gè)索引節(jié)點(diǎn)都會(huì)有Data域廉赔。
- B+樹(shù)所有的Data域在葉子節(jié)點(diǎn)肉微，并且所有葉子節(jié)點(diǎn)之間都有一個(gè)鏈指針。 這樣遍歷葉子節(jié)點(diǎn)就能獲得全部數(shù)據(jù)蜡塌，這樣就能進(jìn)行區(qū)間訪問(wèn)啦碉纳。在數(shù)據(jù)庫(kù)中基于范圍的查詢(xún)是非常頻繁的，而B(niǎo)樹(shù)不支持這樣的遍歷操作馏艾。
缺點(diǎn)：
- B+樹(shù)對(duì)查詢(xún)的優(yōu)化操作會(huì)降低了一定寫(xiě)入性能劳曹。
聚集索引
在MySQL中，選定主鍵之后將會(huì)自動(dòng)為主鍵創(chuàng)建索引琅摩。該索引可以維護(hù)主鍵的唯一性铁孵。非葉子節(jié)點(diǎn)包含了主鍵值，而葉子節(jié)點(diǎn)則指向了一條完整的記錄
非聚集索引
非聚簇索引為什么是二級(jí)索引呢房资？重點(diǎn)在于一個(gè)二字蜕劝。可以料想如果WHERE條件不是根據(jù)主鍵進(jìn)行索引志膀，那么我們就需要基于該非主鍵建立的索引進(jìn)行檢索，這樣建立的索引葉子節(jié)點(diǎn)中包含了記錄的主鍵鳖擒，再使用主鍵在聚簇索引中找尋到完整的記錄溉浙。可以說(shuō)進(jìn)行了兩次B+ Tree查找而不是一次
