1、索引是什么

數(shù)據(jù)庫管理系統(tǒng)中的一個(gè)排序的數(shù)據(jù)結(jié)構(gòu)

三種索引：普通索引、唯一索引、全文索引（一般用ES替代）

數(shù)據(jù)結(jié)構(gòu)模擬器 ： https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

1.1?先了解下幾種常用的查找樹

二分查找樹?Binary Search Tree

左子節(jié)點(diǎn)<父節(jié)點(diǎn)

右子節(jié)點(diǎn)>父節(jié)點(diǎn)

存在一種極端情況，退化成鏈表

查找和插入比較快。但是數(shù)據(jù)樹深度足夠深時(shí)，速度變慢。樹不夠平衡，那么有沒有一種能夠平衡數(shù)據(jù)的樹呢？

平衡二叉樹：AVL Tree

左右子樹深度絕對(duì)值不能超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹 ，怎么理解呢？

左邊樹深度為1，右邊樹深度為2，所以下一個(gè)數(shù)字應(yīng)該保證兩邊深度一致

缺點(diǎn)：頻繁旋轉(zhuǎn)會(huì)使插入和刪除犧牲掉O(logN)左右的時(shí)間，不過相對(duì)二叉查找樹來說，時(shí)間上穩(wěn)定了很多。有沒有更好的解決方式呢?

B-tree（多路搜索樹，并不是二叉的）是一種常見的數(shù)據(jù)結(jié)構(gòu)。使用B-tree結(jié)構(gòu)可以顯著減少定位記錄時(shí)所經(jīng)歷的中間過程，從而加快存取速度。按照翻譯，B 通常認(rèn)為是Balance的簡(jiǎn)稱。這個(gè)數(shù)據(jù)結(jié)構(gòu)一般用于數(shù)據(jù)庫的索引，綜合效率較高

增加了樹杈的節(jié)點(diǎn)，減少了樹的深度，提高了IO的查找速度。有什么缺點(diǎn)？樹杈多了以后，頻繁的分裂合并帶來一定的速度影響？

B+ tree：只在葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，為啥？

B+樹由于非葉節(jié)點(diǎn)只是索引部分，這些節(jié)點(diǎn)中只含有其子樹中的最大(或最小)關(guān)鍵字，當(dāng)非終端節(jié)點(diǎn)上的關(guān)鍵字等于給點(diǎn)值時(shí)，查找并不終止，而是繼續(xù)向下直到葉子節(jié)點(diǎn)。?因此在B+樹中，無論查找成功與否，都是走了一條從根到葉子節(jié)點(diǎn)的路徑 ，保證了查找的穩(wěn)定性。

樹的所有葉結(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表，可以按照關(guān)鍵碼排序的次序遍歷全部記錄

為啥不用紅黑樹呢？

1.紅黑樹最大深度與最小深度不能超過2倍，不夠穩(wěn)定

2.紅黑樹一般放在內(nèi)存里面使用

總結(jié)：AVL Tree?解決了二叉樹不平衡的缺點(diǎn)，B-tree?多叉樹解決了AVL樹高度過高的缺點(diǎn)，B+tree只在葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，葉子節(jié)點(diǎn)形成雙向鏈表，查找數(shù)據(jù)更穩(wěn)定，深度基本固定。