1.什么是數(shù)據(jù)庫的索引

每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，例如二分查找要求被檢索數(shù)據(jù)有序，而二叉樹查找只能應(yīng)用于二叉查找樹上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)(例如，理論上不可能同時將兩列都按順序進(jìn)行組織)，所以，在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用(指向)數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。

在向數(shù)據(jù)庫中插入新的數(shù)據(jù)時，同時也需要向數(shù)據(jù)庫索引中插入相應(yīng)的索引鍵值 ，則需要向 B+樹 中插入新的鍵值。

當(dāng)從數(shù)據(jù)庫中刪除數(shù)據(jù)時，同時也需要從數(shù)據(jù)庫索引中刪除相應(yīng)的索引鍵值 ，則需要從 B+樹 中刪 除該鍵值

在mysql中使用的這種數(shù)據(jù)結(jié)構(gòu)就是B+tree，它是B-tree的變種。

那么什么是B-tree？

2.B-tree

3.B-tree查找

模擬查找關(guān)鍵字29的過程：

根據(jù)根節(jié)點(diǎn)找到磁盤塊1，讀入內(nèi)存。【磁盤I/O操作第1次】

比較關(guān)鍵字29在區(qū)間(17,35)，找到磁盤塊1的指針P2。

根據(jù)P2指針找到磁盤塊3，讀入內(nèi)存。【磁盤I/O操作第2次】

比較關(guān)鍵字29在區(qū)間(26,30)，找到磁盤塊3的指針P2。

根據(jù)P2指針找到磁盤塊8，讀入內(nèi)存。【磁盤I/O操作第3次】

在磁盤塊8中的關(guān)鍵字列表中找到關(guān)鍵字29。

分析上面過程，發(fā)現(xiàn)需要3次磁盤I/O操作，和3次內(nèi)存查找操作。由于內(nèi)存中的關(guān)鍵字是一個有序表結(jié)構(gòu)，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素。B-Tree相對于AVLTree縮減了節(jié)點(diǎn)個數(shù)，使每次磁盤I/O取到內(nèi)存的數(shù)據(jù)都發(fā)揮了作用，從而提高了查詢效率。

4.B-tree的插入和刪除

假設(shè)需依次插入關(guān)鍵字30，26

首先通過查找確定插入的位置。由根a 起進(jìn)行查找，確定30應(yīng)插入的在d 節(jié)點(diǎn)中。由于*d 中關(guān)鍵字?jǐn)?shù)目不超過2(即m-1)，故第一個關(guān)鍵字插入完成：如(b)

同樣，通過查找確定關(guān)鍵字26亦應(yīng)插入 d. 由于d節(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)目超過2，此時需要將 *d分裂成兩個節(jié)點(diǎn)，關(guān)鍵字26及其前、后兩個指針仍保留在 *d 節(jié)點(diǎn)中，而關(guān)鍵字37 及其前、后兩個指針存儲到新的產(chǎn)生的節(jié)點(diǎn) *d中。同時將關(guān)鍵字30 和指示節(jié)點(diǎn) *d的指針插入到其雙親的節(jié)點(diǎn)中。由于 *b節(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目沒有超過2，則插入完成.如(c)(d)

5.B+tree

B+Tree是在B-Tree基礎(chǔ)上的一種優(yōu)化，使其更適合實(shí)現(xiàn)外存儲索引結(jié)構(gòu)， 即B+樹是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B-樹的變形樹。InnoDB存儲引擎就是用B+Tree實(shí)現(xiàn)其索引結(jié)構(gòu)。

從上一節(jié)中的B-Tree結(jié)構(gòu)圖中可以看到每個節(jié)點(diǎn)中不僅包含數(shù)據(jù)的key值，還有data值。而每一個頁的存儲空間是有限的，如果data數(shù)據(jù)較大時將會導(dǎo)致每個節(jié)點(diǎn)(即一個頁)能存儲的key的數(shù)量很小，當(dāng)存儲的數(shù)據(jù)量很大時同樣會導(dǎo)致B-Tree的深度較大，增大查詢時的磁盤I/O次數(shù)，進(jìn)而影響查詢效率。在B+Tree中，所有數(shù)據(jù)記錄節(jié)點(diǎn)都是按照鍵值大小順序存放在同一層的葉子節(jié)點(diǎn)上，而非葉子節(jié)點(diǎn)上只存儲key值信息，這樣可以大大加大每個節(jié)點(diǎn)存儲的key值數(shù)量，降低B+Tree的高度。

B+Tree相對于B-Tree有幾點(diǎn)不同：

非葉子節(jié)點(diǎn)只存儲鍵值信息。

所有葉子節(jié)點(diǎn)之間都有一個鏈指針。

數(shù)據(jù)記錄都存放在葉子節(jié)點(diǎn)中。

6.為什么使用B-Tree(B+Tree)

一般來說，索引本身也很大，不可能全部存儲在內(nèi)存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產(chǎn)生磁盤I/O消耗，相對于內(nèi)存存取，I/O存取的消耗要高幾個數(shù)量級，所以評價(jià)一個數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過程中磁盤I/O操作次數(shù)的漸進(jìn)復(fù)雜度。換句話說，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)。下面先介紹內(nèi)存和磁盤存取原理，然后再結(jié)合這些原理分析B-/+Tree作為索引的效率。

局部性原理與磁盤預(yù)讀

由于存儲介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機(jī)械運(yùn)動耗費(fèi)，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達(dá)到這個目的，磁盤往往不是嚴(yán)格按需讀取，而是每次都會預(yù)讀，即使只需要一個字節(jié)，磁盤也會從這個位置開始，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：

當(dāng)一個數(shù)據(jù)被用到時，其附近的數(shù)據(jù)也通常會馬上被使用。

程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中。

由于磁盤順序讀取的效率很高(不需要尋道時間，只需很少的旋轉(zhuǎn)時間)，因此對于具有局部性的程序來說，預(yù)讀可以提高I/O效率。

預(yù)讀的長度一般為頁(page)的整倍數(shù)。頁是計(jì)算機(jī)管理存儲器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊，每個存儲塊稱為一頁(在許多操作系統(tǒng)中，頁得大小通常為4k)，主存和磁盤以頁為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時，會觸發(fā)一個缺頁異常，此時系統(tǒng)會向磁盤發(fā)出讀盤信號，磁盤會找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁或幾頁載入內(nèi)存中，然后異常返回，程序繼續(xù)運(yùn)行。

B-/+Tree索引的性能分析

從使用磁盤I/O次數(shù)評價(jià)索引結(jié)構(gòu)的優(yōu)劣性：根據(jù)B-Tree的定義，可知檢索一次最多需要訪問h個結(jié)點(diǎn)。數(shù)據(jù)庫系統(tǒng)的設(shè)計(jì)者巧妙的利用了磁盤預(yù)讀原理，將一個結(jié)點(diǎn)的大小設(shè)為等于一個頁面，這樣每個結(jié)點(diǎn)只需要一次I/O就可以完全載入。為了達(dá)到這個目的，在實(shí)際實(shí)現(xiàn)B-Tree還需要使用如下技巧：

每次新建結(jié)點(diǎn)時，直接申請一個頁面的空間，這樣可以保證一個結(jié)點(diǎn)的大小等于一個頁面，加之計(jì)算機(jī)存儲分配都是按頁對齊的，就實(shí)現(xiàn)了一個node只需一次I/O。

B-Tree中一次檢索最多需要h-1次I/O(根結(jié)點(diǎn)常駐內(nèi)存)，漸進(jìn)復(fù)雜度為O(h)=O(logdN)。一般實(shí)際應(yīng)用中，出讀d是非常大的數(shù)字，通常超過100，因此h非常小。

綜上所述，用B-Tree作為索引結(jié)構(gòu)效率是非常高的。

而紅黑樹結(jié)構(gòu)，h明顯要深得多。由于邏輯上很近的結(jié)點(diǎn)(父子結(jié)點(diǎn))物理上可能離得很遠(yuǎn)，無法利用局部性原理。所以即使紅黑樹的I/O漸進(jìn)復(fù)雜度也為O(h)，但是查找效率明顯比B-Tree差得多。

B+Tree更適合外存索引，是和內(nèi)結(jié)點(diǎn)出度d有關(guān)。從上面分析可以看到，d越大索引的性能越好，而出度的上限取決于結(jié)點(diǎn)內(nèi)key和data的大小：dmax=floor(pagesize/(keysize+datasize+pointsize))。

floor表示向下取整。由于B+Tree內(nèi)結(jié)點(diǎn)去掉了data域，因此可以擁有更大的出度，擁有更好的性能。

7.MyISAM索引實(shí)現(xiàn)

1.主鍵索引

MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)，葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址。

2.輔助索引

在MyISAM中，主索引和輔助索引(Secondary key)在結(jié)構(gòu)上沒有任何區(qū)別，只是主索引要求key是唯一的，而輔助索引的key可以重復(fù)。如果我們在Col2上建立一個輔助索引，則此索引的結(jié)構(gòu)如下圖所示：

8.InnoDB索引實(shí)現(xiàn)

1.InnoDB主鍵索引

InnoDB中，表數(shù)據(jù)文件本身就是按B+Tree組織的一個索引結(jié)構(gòu)，這棵樹的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄。這個索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引。

2.InnoDB輔助索引

InnoDB的所有輔助索引都引用主鍵作為data域。例如，下圖為定義在Col3上的一個輔助索引：

InnoDB存儲引擎中有頁(Page)的概念，頁是其磁盤管理的最小單位。InnoDB存儲引擎中默認(rèn)每個頁的大小為16KB，可通過參數(shù)innodb_page_size將頁的大小設(shè)置為4K、8K、16K，在MySQL中可通過如下命令查看頁的大小：show variables like 'innodb_page_size';

系統(tǒng)從磁盤讀取數(shù)據(jù)到內(nèi)存時是以磁盤塊(block)為基本單位的，位于同一個磁盤塊中的數(shù)據(jù)會被一次性讀取出來，而不是需要什么取什么。

而系統(tǒng)一個磁盤塊的存儲空間往往沒有這么大，因此InnoDB每次申請磁盤空間時都會是若干地址連續(xù)磁盤塊來達(dá)到頁的大小16KB。InnoDB在把磁盤數(shù)據(jù)讀入到磁盤時會以頁為基本單位，在查詢數(shù)據(jù)時如果一個頁中的每條數(shù)據(jù)都能有助于定位數(shù)據(jù)記錄的位置，這將會減少磁盤I/O次數(shù)，提高查詢效率。

.推算

InnoDB存儲引擎中頁的大小為16KB，一般表的主鍵類型為INT(占用4個字節(jié))或BIGINT(占用8個字節(jié))，指針類型也一般為4或8個字節(jié)，也就是說一個頁(B+Tree中的一個節(jié)點(diǎn))中大概存儲16KB/(8B+8B)=1K個鍵值(因?yàn)槭枪乐?#xff0c;為方便計(jì)算，這里的K取值為〖10〗3)。也就是說一個深度為3的B+Tree索引可以維護(hù)103 * 10^3 * 10^3 = 10億 條記錄。

實(shí)際情況中每個節(jié)點(diǎn)可能不能填充滿，因此在數(shù)據(jù)庫中，B+Tree的高度一般都在24層。mysql的InnoDB存儲引擎在設(shè)計(jì)時是將根節(jié)點(diǎn)常駐內(nèi)存的，也就是說查找某一鍵值的行記錄時最多只需要13次磁盤I/O操作。

9.數(shù)據(jù)庫中的B+Tree索引可以分為聚集索引(clustered index)和輔助索引(secondary index)

聚集索引的B+Tree中的葉子節(jié)點(diǎn)存放的是整張表的行記錄數(shù)據(jù)。輔助索引與聚集索引的區(qū)別在于輔助索引的葉子節(jié)點(diǎn)并不包含行記錄的全部數(shù)據(jù)，而是存儲相應(yīng)行數(shù)據(jù)的聚集索引鍵，即主鍵。當(dāng)通過輔助索引來查詢數(shù)據(jù)時，InnoDB存儲引擎會遍歷輔助索引找到主鍵，然后再通過主鍵在聚集索引中找到完整的行記錄數(shù)據(jù)。

InnoDB索引和MyISAM索引的區(qū)別：

一是主索引的區(qū)別，InnoDB的數(shù)據(jù)文件本身就是索引文件。而MyISAM的索引和數(shù)據(jù)是分開的。

二是輔助索引的區(qū)別：InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值而不是地址。而MyISAM的輔助索引和主索引沒有多大區(qū)別。

所以：

1.不建議使用過長的字段作為主鍵，因?yàn)樗休o助索引都引用主索引，過長的主索引會令輔助索引變得過大

2.用非單調(diào)的字段作為主鍵在InnoDB中不是個好主意，因?yàn)镮nnoDB數(shù)據(jù)文件本身是一顆B+Tree，非單調(diào)的主鍵會造成在插入新記錄時數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。

總結(jié)

以上是生活随笔為你收集整理的mysql 二叉树表设计_mysql---B+tree索引的设计原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。