1.mysql索引類型

1.1B-樹索引

(B-樹就是所說的B樹)
使用樹狀結(jié)構(gòu)存儲數(shù)據(jù)庫索引可以保證有序性而且查詢效率也很高，但是為什么數(shù)據(jù)庫的索引沒有使用二叉查找樹O(logN)來實(shí)現(xiàn)數(shù)據(jù)庫的索引那？因?yàn)槲覀儾坏貌豢紤]一個(gè)很現(xiàn)實(shí)的問題那就是數(shù)據(jù)庫的索引是存儲在硬盤上的，當(dāng)數(shù)據(jù)量比較大的時(shí)候，索引甚至可能有幾個(gè)G,我們無法將索引一次加入到內(nèi)存當(dāng)中，只能逐頁的加載每一個(gè)磁盤頁。最壞的情況下磁盤IO的次數(shù)就是樹的深度。為了減少磁盤IO次數(shù)我們就要降低樹的高度。
B樹是一種多路平衡查找樹，它的每一個(gè)結(jié)點(diǎn)最多包含K個(gè)孩子，k稱為B樹的階，k取決于磁盤頁的大小。

1.1.1一個(gè)m階的B樹必須滿足以下條件：

1.根結(jié)點(diǎn)至少有兩個(gè)子女。
2.每個(gè)非葉子節(jié)點(diǎn)都包含k-1個(gè)元素和k個(gè)孩子，其中 m/2 <= k <= m
3.每一個(gè)葉子節(jié)點(diǎn)都包含k-1個(gè)元素，其中 m/2 <= k <= m
4.所有的葉子結(jié)點(diǎn)都位于同一層。
5.每個(gè)節(jié)點(diǎn)中的元素從小到大排列，節(jié)點(diǎn)當(dāng)中k-1個(gè)元素正好是k個(gè)孩子包含的元素的值域分劃。

1 2 3 5 6 8 9 11 12 13 15
m=3;
k={2,3}
非葉子節(jié)點(diǎn)孩子={2，3}
非葉子節(jié)點(diǎn)元素={1, 2}
葉子節(jié)點(diǎn)元素= {1，2}

圖片.png

利用這種特性可以減少磁盤IO的次數(shù)，雖然可能查詢的次數(shù)變多一點(diǎn)但是相比于磁盤IO的速度內(nèi)存耗時(shí)幾乎可以忽略不計(jì)。

1.1.2B樹如何插入刪除

假如要插入4

自上到下查找發(fā)現(xiàn)3<4<=5,但是節(jié)點(diǎn)3，5已經(jīng)是兩元素節(jié)點(diǎn)，無法再增加。父親節(jié)點(diǎn) {2，6 }也是兩元素節(jié)點(diǎn)，也無法再增加。根節(jié)點(diǎn)9是單元素節(jié)點(diǎn)，可以升級為兩元素節(jié)點(diǎn)。于是拆分節(jié)點(diǎn){3，5}與節(jié)點(diǎn){2，6}，讓根節(jié)點(diǎn)9升級為兩元素節(jié)點(diǎn){4，9}。節(jié)點(diǎn)6獨(dú)立為根節(jié)點(diǎn)的第二個(gè)孩子。

圖片.png

假如要刪除11

刪除11后，節(jié)點(diǎn)12只有一個(gè)孩子，不符合B樹規(guī)范。因此找出12,13,15三個(gè)節(jié)點(diǎn)的中位數(shù)13，取代節(jié)點(diǎn)12，而節(jié)點(diǎn)12自身下移成為第一個(gè)孩子。（這個(gè)過程稱為左旋）

圖片.png

1.2B+樹

當(dāng)索引項(xiàng)比較多的時(shí)候，不能一次裝入內(nèi)存，可以對索引再建立索引，形成多級索引。

1.2.1B+樹的特征

一個(gè)m階的B+樹具有如下幾個(gè)特征：
除了和B樹有相同的特征外B+樹還要滿足以下的特征
1.非葉子節(jié)點(diǎn)包含有k個(gè)元素（B樹中是k-1個(gè)元素），每個(gè)元素不保存數(shù)據(jù)，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。m/2<=k<=m

2.所有的葉子結(jié)點(diǎn)中包含了全部元素的信息，及指向含這些元素記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。

3.所有的非葉子節(jié)點(diǎn)元素都同時(shí)存在于子節(jié)點(diǎn)，在子節(jié)點(diǎn)元素中是最大（或最?。┰?/p>

圖片.png

1.2.2B+樹的優(yōu)勢

• 單行查詢
  因?yàn)锽+樹的非葉子節(jié)點(diǎn)并不存儲數(shù)據(jù)記錄，而是只存儲索引所以相同大小的磁盤也可以存儲更多的節(jié)點(diǎn)元素，所以在單行查詢時(shí)磁盤IO的次數(shù)更少。并且B+樹查詢最終查詢必須在葉子節(jié)點(diǎn)上，而B樹最好的情況只查詢根節(jié)點(diǎn)，最壞要要查詢?nèi)~子節(jié)點(diǎn)，所以B+樹是穩(wěn)定的而B樹是不穩(wěn)定查詢。
• 范圍查詢
  B+樹只需要定位到最小的元素，然后遍歷葉子節(jié)點(diǎn)的鏈表就能查詢到所有的元素，而B樹要每次都從上到下依次前序遍歷到每一個(gè)元素。
• 總結(jié)：

1. 單一節(jié)點(diǎn)存儲更多的元素，使得查詢的IO次數(shù)更少。

2. 所有查詢都要查找到葉子節(jié)點(diǎn)，查詢性能穩(wěn)定。

3. 所有葉子節(jié)點(diǎn)形成有序鏈表，便于范圍查詢。

1.2.3插入和刪除

B+樹的插入和刪除和B+樹類似，最重要的區(qū)別就是節(jié)點(diǎn)指針的調(diào)整。

注：這里只是介紹了最常用兩種索引原理，其他索引將在后面穿插介紹。