mysql怎么用b樹索引,mysql索引的數(shù)據(jù)結(jié)構(gòu),為什么用B+樹不用B樹

MySQL BTREE索引

個人能力有限，如有錯誤請指出，共同學(xué)習(xí)。

廣靈網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,廣靈網(wǎng)站設(shè)計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為廣靈上千家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站制作要多少錢，請找那個售后服務(wù)好的廣靈做網(wǎng)站的公司定做！

二叉樹

B樹

B+樹

特點：

聚簇索引

二級索引

key數(shù)據(jù)存儲量估算：

若每個頁可以存1000個key，而且樹的高度是4，那么

前提條件如下：

插入步驟

步驟一

因為索引中還沒有數(shù)據(jù)，所以此時的B+樹只有一個空的根結(jié)點，又由于一個頁只能存3個key，首先將10，20，5插入進去（實際上此步發(fā)生了3次插入），然后在頁面內(nèi)做數(shù)據(jù)排序，最終結(jié)果如下圖：

步驟二：

由于根頁面已經(jīng)寫滿，此時插入8，將發(fā)生分裂（根頁面分裂），大致步驟如下：

注意：在分裂過程中，根結(jié)點始終是不會變的，不管變成多大的樹，根結(jié)點的頁面號始終如一。

步驟五：

插入數(shù)據(jù)40，發(fā)現(xiàn)比根結(jié)點23大，找到103號頁面，發(fā)現(xiàn)已滿，執(zhí)行分裂，分裂同上面葉子結(jié)點的分裂步驟。分裂后如圖所示：

步驟六：

繼續(xù)插入下一個數(shù)據(jù)9，因為比20小，找到101號頁面，發(fā)現(xiàn)已滿，需要做葉子結(jié)點分裂，如下圖：

傳統(tǒng)B+樹的數(shù)據(jù)刪除，一般都會有一個所謂的填充因子，來控制頁面數(shù)據(jù)的刪除比例，如果數(shù)據(jù)量小于這個填充因子所表示的數(shù)據(jù)量，就會有節(jié)點合并，這與分裂是相對應(yīng)的。

InnoDB的實現(xiàn)與傳統(tǒng)B+樹算法有不同之處，InnoDB在刪除索引數(shù)據(jù)時，會先檢查當(dāng)前頁剩余的記錄數(shù)，如果只剩下一條記錄，就會直接將這個頁面從B+樹中摘除，也只有這種情況，InnoDB才會回收一個頁面，InnoDB的頁面沒有合并一說，但是對于根節(jié)點，即使索引數(shù)據(jù)全部刪除，根節(jié)點頁依然存在，只不過是以空頁的形式存在。

下面舉個例子描述索引刪除過程，前提條件與前面插入記錄時一致。

刪除數(shù)據(jù) 50

刪除過程全部結(jié)束，最終得到一個空的索引頁。

《MySQL運維內(nèi)參》

B+樹動畫演示：

Mysql InnoDB索引原理

理解Mysql索引的原理和數(shù)據(jù)結(jié)構(gòu)有助于我們更好的使用索引以及進行SQL優(yōu)化，索引是在存儲引擎層面實現(xiàn)的，所以不同的引擎實現(xiàn)的索引也有一定的區(qū)別，但是在生產(chǎn)環(huán)境中，我們最常用的就是InnoDB引擎和B樹索引，OK，那本文要討論的重點也同樣是 InnoDB引擎下的B樹索引 。

我們建立一個表來進行測試，表的DDL如下所示，我們要關(guān)注的是表t_book上的主鍵索引id和name author publish_date三列組成的索引test_index。

Mysql中的B樹索引是使用B+樹實現(xiàn)的，關(guān)于B+樹的數(shù)據(jù)結(jié)構(gòu)個人認為美團點評技術(shù)博客中Mysql索引原理及慢查詢優(yōu)化一文中介紹的非常詳實，B+樹的數(shù)據(jù)結(jié)構(gòu)如下圖所示。

圖中淺藍色塊即磁盤塊，根節(jié)點磁盤塊中存儲17和35兩個數(shù)據(jù)，其中指針P1指向小于17的數(shù)據(jù)，指針P2指向大于17小于35的數(shù)據(jù)，指針P3指向大于35的數(shù)據(jù)。顯然通過B+樹索引查詢數(shù)據(jù)與B+樹的高度有關(guān)，如上圖的B+樹索引查找一個葉子節(jié)點的數(shù)據(jù)只需要三次磁盤IO，對于Mysql來說三層的B+樹可以索引上百萬的數(shù)據(jù)，這對于查詢效率的提升是巨大的。

總結(jié)起來Mysql中B樹索引有以下關(guān)鍵特點：

Mysql中的B樹索引有兩種數(shù)據(jù)存儲形式，一種為聚簇索引，一種為二級索引。

InnoDB一般會使用表的主鍵來作為聚簇索引，如果一個表沒有主鍵（不建議這么玩）InnoDB會選用一個唯一非空索引來代替，如果沒有這樣的索引，InnoDB會隱式建立一個聚簇索引。聚簇的含義即是數(shù)據(jù)行和相鄰的鍵值緊湊的存儲在一起，占據(jù)一塊連續(xù)的磁盤空間，因此通過聚簇索引訪問數(shù)據(jù)可以有效減少隨機IO，通常使用聚簇索引查找比非聚簇索引查找速度更快。以我們建立的表t_book為例，聚簇索引即為自增主鍵id，其B樹索引數(shù)據(jù)結(jié)構(gòu)可以用下圖來表示。

聚簇索引有以下關(guān)鍵特點：

InnoDB的B樹索引中除了聚簇索引，就都是二級索引了，二級索引的含義是索引的葉子節(jié)點除了存儲了索引值，還存儲了主鍵id，在使用二級索引進行查詢時，查找到二級索引B樹上的葉子節(jié)點后還需要去聚簇索引上去查詢真實數(shù)據(jù)，但是這里有一種特殊情況，即查詢所需的所有字段在二級索引中都可以獲取，此時就不需要再去回表查數(shù)據(jù)了，這種情況就是索引覆蓋（EXPLAIN中EXTRA列中會出現(xiàn)USING INDEX，本文只關(guān)注索引結(jié)構(gòu)，不詳細討論索引覆蓋等技術(shù)的使用，如果深入理解索引的數(shù)據(jù)結(jié)構(gòu)，索引覆蓋等技術(shù)也沒有那么神秘）。

在我們的測試表t_book中，test_index即為二級索引，由于我們把除了主鍵id所有的列都作為一個聯(lián)合索引，所以在這個表上的查詢都可以使用索引覆蓋技術(shù)，但是具體生產(chǎn)環(huán)境中也不建議總是采用這種做法，索引列的增加也會增大插入更新數(shù)據(jù)時的索引更新成本，具體的優(yōu)化要視具體情況決策。t_book上的二級索引test_index的索引結(jié)構(gòu)由下圖表示。

通過以上結(jié)構(gòu)，我們可以推斷出二級索引的以下關(guān)鍵特點：

索引覆蓋：

最左前綴匹配：

二級索引可以說是我們在Mysql中最常用的索引，通過理解二級索引的索引結(jié)構(gòu)可以更容易理解二級索引的特性和使用。

最后聊點輕松的索引結(jié)構(gòu)，哈希索引就是通過哈希表實現(xiàn)的索引，即通過被索引的列計算出哈希值，并指向被索引的記錄。

哈希索引有如下特性：

Mysql索引原理及慢查詢優(yōu)化

高性能Mysql 第三版

mysql中的索引怎樣使用btree索引

B-Tree 索引是 MySQL 數(shù)據(jù)庫中使用最為頻繁的索引類型，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支持 B-Tree 索引。不僅僅在 MySQL 中是如此，實際上在其他的很多數(shù)據(jù)庫管理系統(tǒng)中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因為 B-Tree 索引的存儲結(jié)構(gòu)在數(shù)據(jù)庫的數(shù)據(jù)檢 索中有非常優(yōu)異的表現(xiàn)。

一般來說， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結(jié)構(gòu)來存儲的，也就是所有實際需要的數(shù)據(jù)都存放于 Tree 的 Leaf Node ，而且到任何一個 Leaf Node 的最短路徑的長度都是完全相同的，所以我們大家都稱之為 B-Tree 索引當(dāng)然，可能各種數(shù)據(jù)庫（或 MySQL 的各種存儲引擎）在存放自己的 B-Tree 索引的時候會對存儲結(jié)構(gòu)稍作改造。如 Innodb 存儲引擎的 B-Tree 索引實際使用的存儲結(jié)構(gòu)實際上是 B+Tree ，也就是在 B-Tree 數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上做了很小的改造，在每一個

Leaf Node 上面出了存放索引鍵的相關(guān)信息之外，還存儲了指向與該 Leaf Node 相鄰的后一個 LeafNode 的指針信息，這主要是為了加快檢索多個相鄰 Leaf Node 的效率考慮。

在 Innodb 存儲引擎中，存在兩種不同形式的索引，一種是 Cluster 形式的主鍵索引（ Primary Key ），另外一種則是和其他存儲引擎（如 MyISAM 存儲引擎）存放形式基本相同的普通 B-Tree 索引，這種索引在 Innodb 存儲引擎中被稱為 Secondary Index 。

mysql采用哪些索引，B樹索引解釋下

事實上，在MySQL數(shù)據(jù)庫中，諸多存儲引擎使用的是B+樹，即便其名字看上去是BTREE。

4.1 innodb的索引機制

先以innodb存儲引擎為例，說明innodb引擎是如何利用B+樹建立索引的

首先創(chuàng)建一張表：zodiac，并插入一些數(shù)據(jù)

對于innodb來說，只有一個數(shù)據(jù)文件，這個數(shù)據(jù)文件本身就是用B+樹形式組織，B+樹每個節(jié)點的關(guān)鍵字就是表的主鍵，因此innode的數(shù)據(jù)文件本身就是主索引文件，如下圖所示，主索引中的葉子頁（leaf page）包含了數(shù)據(jù)記錄，但非葉子節(jié)點只包含了主鍵，術(shù)語“聚簇”表示數(shù)據(jù)行和相鄰的鍵值緊湊地存儲在一起，因此這種索引被稱為聚簇索引，或聚集索引。

這種索引方式，可以提高數(shù)據(jù)訪問的速度，因為索引和數(shù)據(jù)是保存在同一棵B樹之中，從聚簇索引中獲取數(shù)據(jù)通常比在非聚簇索引中要來得快。

所以可以說，innodb的數(shù)據(jù)文件是依靠主鍵組織起來的，這也就是為什么innodb引擎下創(chuàng)建的表，必須指定主鍵的原因，如果沒有顯式指定主鍵，innodb引擎仍然會對該表隱式地定義一個主鍵作為聚簇索引。

同樣innodb的輔助索引，如下圖所示，假設(shè)這些字符是按照生肖的順序排列的（其實我也不知道具體怎么實現(xiàn)，不要在意這些細節(jié)，就是舉個例子），其葉子節(jié)點中也包含了記錄的主鍵，因此innodb引擎在查詢輔助索引的時候會查詢兩次，首先通過輔助索引得到主鍵值，然后再查詢主索引，略微有點啰嗦

MySQL索引

MySQL的Innodb存儲引擎的索引分為聚集索引和非聚集索引兩大類

特點：B+樹葉子節(jié)點存儲行數(shù)據(jù)

一個表中，必須有一個聚集索引，只能有一個聚集索引，Innodb通常把一個表的主鍵索引作為聚集索引，如果沒有主鍵InnoDB會選擇一個唯一索引代替。如果沒有這樣的索引，InnoDB會隱式的定義一個主鍵來作為聚集索引，這個字段為6個字節(jié)，類型為長整形。

利用主鍵索引查找行數(shù)據(jù)是最快的，建議使用自增主鍵原因是利于索引樹的構(gòu)建（主鍵自增寫入時新插入的數(shù)據(jù)不會影響到原有頁，插入效率高；但是如果主鍵是無序的或者隨機的，那每次的插入可能會導(dǎo)致原有頁頻繁的分裂，影響插入效率）

特點：B+樹葉子節(jié)點存儲主鍵ID

一個表中可以有多個非聚集索引，每個非聚集索引即是一棵B+樹

通過非聚集索引查找數(shù)據(jù)時，需要先在非聚集索引上找到主鍵ID，再從聚集索引獲取行數(shù)據(jù)，這個過程就稱之為回表

B樹索引中的B樹實際上是B+樹，至于為什么使用B+樹而不使用B樹或者紅黑樹的原因在另外的文章中有提及。

特點：

特點：類似JDK中的HashMap，但無法支持范圍查詢

特點：使用的算法仍然是B樹索引，不同的就是索引列的值必須唯一

對于普通索引來說，查找到滿足條件的第一個記錄后，需要查找下一個記錄，直到碰到第一個不滿足條件的記錄。

對于唯一索引來說，由于索引定義了唯一性，查找到第一個滿足條件的記錄后，就會停止繼續(xù)檢索，提升索引性能

另外插入行時會構(gòu)建該唯一索引，假如索引值重復(fù)將插入失敗，適合業(yè)務(wù)上做唯一性檢驗

通過建立倒排索引，可以極大的提升檢索效率,解決判斷字段是否包含的問題，但是業(yè)務(wù)上一般都不采用這種索引，而是使用ES處理全文搜索需求

僅對某個特定字段建立的索引，如(biz_id)

對多個字段建立的索引，如(biz_id,type)

新聞名稱：mysql怎么用b樹索引,mysql索引的數(shù)據(jù)結(jié)構(gòu),為什么用B+樹不用B樹
轉(zhuǎn)載注明：http://muchs.cn/article46/phgceg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、面包屑導(dǎo)航、全網(wǎng)營銷推廣、移動網(wǎng)站建設(shè)、企業(yè)建站、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)