Mysql索引實現：

B-tree，B是balance，一般用于數據庫的索引。使用B-tree結構可以顯著減少定位記錄時所經歷的中間過程，從而加快存取速度。而B+tree是B-tree的一個變種，MySQL就普遍使用B+tree實現其索引結構。

一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產生磁盤I/O消耗，相對于內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。

為了達到這個目的，磁盤按需讀取，要求每次都會預讀的長度一般為頁的整數倍。而且數據庫系統將一個節點的大小設為等于一個頁，這樣每個節點只需要一次I/O就可以完全載入。每次新建節點時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個node只需一次I/O。并把B-tree中的m值設的非常大，就會讓樹的高度降低，有利于一次完全載入

B-Way查找樹：

一棵樹的每個節點的度小于等于m。

每個節點的鍵值數小于m每個節點的度小于等于m鍵值按順序排列子樹的鍵值要完全小于或大于或介于父節點之間的鍵值

B-Tree樹：

B-tree又叫平衡多路查找樹。一棵m階的B-tree (m叉樹)的特性如下：

(其中ceil(x)是一個取上限的函數)

1) 樹中每個結點至多有m個孩子；

2) 除根結點和葉子結點外，其它每個結點至少有有ceil(m / 2)個孩子；

3) 若根結點不是葉子結點，則至少有2個孩子(特殊情況：沒有孩子的根結點，即根結點為葉子結點，整棵樹只有一個根節點)；

4) 所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字信息(可以看做是外部結點或查詢失敗的結點，實際上這些結點不存在，指向這些結點的指針都為null)；

5) 每個非終端結點中包含有n個關鍵字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：

a) Ki (i=1...n)為關鍵字，且關鍵字按順序排序K(i-1)< Ki。

b) Pi為指向子樹根的接點，且指針P(i-1)指向子樹種所有結點的關鍵字均小于Ki，但都大于K(i-1)。

c) 關鍵字的個數n必須滿足： ceil(m / 2)-1 <= n <= m-1。

B+Tree樹：

B+樹是B-樹的變體。

有幾點不同的地方：

非葉子結點的子樹指針與關鍵字個數相同

為所有葉子結點增加一個鏈指針

所有關鍵字都在葉子結點出現

二、聚集索引, 非聚集索引

聚集索引：

該索引中鍵值的邏輯順序決定了表中相應行的物理順序。

聚集索引確定表中數據的物理順序。聚集索引類似于電話簿，后者按姓氏排列數據。由于聚集索引規定數據在表中的物理存儲順序，因此一個表只能包含一個聚集索引。但該索引可以包含多個列(組合索引)，就像電話簿按姓氏和名字進行組織一樣。

非聚集索引：

該索引中索引的邏輯順序與磁盤上行的物理存儲順序不同。

索引是通過二叉樹的數據結構來描述的，我們可以這么理解聚簇索引：索引的葉節點就是數據節點。而非聚簇索引的葉節點仍然是索引節點，只不過有一個指針指向對應的數據塊。如下圖：

總結

以上是生活随笔為你收集整理的mysql索引 聚集索引_Mysql 索引实现原理. 聚集索引, 非聚集索引的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。