MySQL BTREE索引

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

創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比青白江網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式青白江網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋青白江地區(qū)。費用合理售后完善，十載實體公司更值得信賴。

二叉樹

B樹

B+樹

特點：

聚簇索引

二級索引

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

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

前提條件如下：

插入步驟

步驟一

因為索引中還沒有數(shù)據(jù)，所以此時的B+樹只有一個空的根結(jié)點，又由于一個頁只能存3個key，首先將10，20，5插入進(jìn)去（實際上此步發(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+樹動畫演示：

聚集索引可以用b樹實現(xiàn)么

聚集索引可以用b樹實現(xiàn)。

簡介：

B+樹中只有葉子節(jié)點會帶有指向記錄的指針，而B樹則所有節(jié)點都帶有。

B+樹索引可以分為聚集索引和非聚集索引。

mysql使用B+樹，其中Myisam是非聚集索引，innoDB是聚集索引。

聚簇索引索引的葉節(jié)點就是數(shù)據(jù)節(jié)點；而非聚簇索引的葉節(jié)點仍然是索引節(jié)點，只不過有一個指針指向?qū)?yīng)的數(shù)據(jù)塊。

B+ 樹的特點:

（1）所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中(稠密索引)，且鏈表中的關(guān)鍵字恰好是有序的。

（2）不可能在非葉子結(jié)點命中。

（3）非葉子結(jié)點相當(dāng)于是葉子結(jié)點的索引(稀疏索引)，葉子結(jié)點相當(dāng)于是存儲(關(guān)鍵字)數(shù)據(jù)的數(shù)據(jù)層。

Mysql InnoDB b+樹的高度

為什么Mysql考慮使用B+樹，而不是B樹，其實我們可以先了解下B樹和B+樹的特點來看下。

※ 樹的每個結(jié)點都會存儲數(shù)據(jù)

※ 單次查詢不一定要遍歷到樹的根部，平均查詢時間會比較快

※ 非葉子節(jié)點不存儲數(shù)據(jù)，只存儲（冗余）索引，索引包含主鍵和指針

※ 葉子節(jié)點才真正存儲數(shù)據(jù)

※ 每個葉子節(jié)點互相鏈表相連，保證了范圍查詢的時效性(頁之間用雙向鏈表連接，數(shù)據(jù)間用單項鏈表鏈接)

InnoDB最小存儲單位是頁，葉子節(jié)點和非葉子節(jié)點最小單位都是頁，頁大小Mysql 默認(rèn)設(shè)定16384字節(jié)，約為16KB。

我們假設(shè)主鍵ID為bigint類型，長度為8字節(jié)，而指針大小在InnoDB源碼中設(shè)置為6字節(jié)，這樣一共14字節(jié)

我們一個頁中能存放多少這樣的索引元素，其實就代表有多少指針，即16384/14=1170;

高度為2的B+樹能存放1170×16=18720

高度為3的B+樹能存放1170×1170×16 = 21902400

InnoDB中B+樹高度一般為1-3層，它就能滿足千萬級的數(shù)據(jù)存儲。

在查找數(shù)據(jù)時一次頁的查找代表一次IO，所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數(shù)據(jù)。

Mysql InnoDB索引原理

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

我們建立一個表來進(jìn)行測試，表的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)個人認(rèn)為美團(tuán)點評技術(shù)博客中Mysql索引原理及慢查詢優(yōu)化一文中介紹的非常詳實，B+樹的數(shù)據(jù)結(jié)構(gòu)如下圖所示。

圖中淺藍(lán)色塊即磁盤塊，根節(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，在使用二級索引進(jìn)行查詢時，查找到二級索引B樹上的葉子節(jié)點后還需要去聚簇索引上去查詢真實數(shù)據(jù)，但是這里有一種特殊情況，即查詢所需的所有字段在二級索引中都可以獲取，此時就不需要再去回表查數(shù)據(jù)了，這種情況就是索引覆蓋（EXPLAIN中EXTRA列中會出現(xiàn)USING INDEX，本文只關(guān)注索引結(jié)構(gòu)，不詳細(xì)討論索引覆蓋等技術(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使用基礎(chǔ)、進(jìn)階分享

MySQL是一個關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，由瑞典MySQL AB公司開發(fā)，屬于Oracle旗下產(chǎn)品，是最流行的關(guān)系型數(shù)據(jù)庫管理系統(tǒng)之一。

端口是3306。

表很多時，使用linux腳本，需要根據(jù)需要修改一下：

和創(chuàng)建一樣，可以加上 if exists

可兩篇文章：

如：

用于在已有的表中添加、刪除或修改列。

添加 ADD

或

默認(rèn)是添加到最后，但可以指定位置。 FIRST ：添加最前

AFTER 字段名 ：添加指定字段之后

例子：

刪除 DROP

修改 MODIFY 主要修改原列的類型或約束條件 同樣可以用 FIRST 和 AFTER 字段名 ，代表的是修改到哪里。

修改字段名 CHANGE

可以把表2的數(shù)據(jù)復(fù)制到表1中，但 不能復(fù)制約束性條件 。

單行

多行，注意 只有一個VALUES ：

不寫 (行1, 行2...) 這一部分的話，默認(rèn)一一對應(yīng)

除了以上方法外，還可以用SET為每一行附上相應(yīng)的值。

假如沒有篩選的話，就給全部都修改了。可以用 WHERE 篩選。

假如 沒有篩選的話，就給全部刪除了 。相當(dāng)于清空。

清空

先把表刪除，然后再建一個。與 DELETE FROM 相比， TRUNCATE 的效率更快，因為 DELETE FROM 是把記錄逐條刪除的。

查詢執(zhí)行的順序

FROM -- WHERE -- SELECT -- GROUP BY -- HAVING -- ORDER BY -- LIMIT

注意

當(dāng)數(shù)據(jù)很大，上百萬的時候，使用LIMIT ... OFFSET ..的方式進(jìn)行分頁十分浪費資源且耗時長。最好是結(jié)合WHERE使用，如：

REGEXP 使用正則表達(dá)進(jìn)行匹配。 查詢時，需要搭配WHERE或HAVING使用 。

兩個表之間有交集且要用到兩個表的數(shù)據(jù)時，可以使用內(nèi)連接查詢。

LEFT JOIN 關(guān)鍵字從左表（table1）返回所有的行，即使右表（table2）中沒有匹配。如果右表中沒有匹配，則結(jié)果為 NULL。

用法：

RIGHT JOIN 關(guān)鍵字從右表（table2）返回所有的行，即使左表（table1）中沒有匹配。如果左表中沒有匹配，則結(jié)果為 NULL。 把LEFT JOIN的表1、表2調(diào)換順序，就是REGHT JOIN 。

FULL OUTER JOIN 關(guān)鍵字只要左表（table1）和右表（table2）其中一個表中存在匹配，則返回行. 相當(dāng)于結(jié)合了 LEFT JOIN 和 RIGHT JOIN 的結(jié)果。

但 MySQL中不支持 FULL OUTER JOIN 。

即SELECT嵌套。

IN 一個查詢結(jié)果作為另一個查詢的條件。 如：

EXISTS 用于判斷查詢子句是否有記錄，如果有一條或多條記錄存在返回 True，否則返回 False。True時執(zhí)行。 如：

索引的本質(zhì)是一種排好序的數(shù)據(jù)結(jié)構(gòu)。利用索引可以提高查詢速度。

常見的索引有：

MySQL通過外鍵約束來保證表與表之間的數(shù)據(jù)的完整性和準(zhǔn)確性。 外鍵的使用條件：

外鍵的好處：可以使得兩張表關(guān)聯(lián)，保證數(shù)據(jù)的一致性和實現(xiàn)一些級聯(lián)操作。

對已有的兩個表增加外鍵 比如：主表為A，子表為B，外鍵為aid，外鍵約束名字為a_fk_b

為子表添加一個字段，當(dāng)做外鍵

為子表添加外鍵約束條件

假如刪除記錄報錯： [Err] 1451 -Cannot deleteorupdatea parent row: aforeignkeyconstraintfails (...)

這是因為MySQL中設(shè)置了foreign key關(guān)聯(lián)，造成無法更新或刪除數(shù)據(jù)。可以通過設(shè)置 FOREIGN_KEY_CHECKS 變量來避免這種情況。 第一步：禁用外鍵約束，我們可以使用： SETFOREIGN_KEY_CHECKS=0; 第二步：刪除數(shù)據(jù) 第三步：啟動外鍵約束，我們可以使用： SETFOREIGN_KEY_CHECKS=1; 查看當(dāng)前FOREIGN_KEY_CHECKS的值，可用如下命令： SELECT @@FOREIGN_KEY_CHECKS;

使用 UNION 來組合兩個查詢，如果第一個查詢返回 M 行，第二個查詢返回 N 行，那么組合查詢的結(jié)果一般為 M+N 行。

每個查詢必須包含相同的列、表達(dá)式和聚集函數(shù)。

默認(rèn)會去除相同行，如果需要 保留 相同行，使用 UNION ALL 。

只能包含一個 ORDER BY 子句，并且必須位于語句的最后 。

內(nèi)置函數(shù)很多, 見: MySQL 函數(shù)

我們一般使用 START TRANSACTION 或 BEGIN 開啟事務(wù), COMMIT 提交事務(wù)中的命令, SAVEPOINT : 相當(dāng)于設(shè)置一個還原點, ROLLBACK TO : 回滾到某個還原點下

一般的使用格式如下:

開啟事務(wù)時, 默認(rèn)加鎖

根據(jù)類型可分為共享鎖（SHARED LOCK）和排他鎖（EXCLUSIVE LOCK）或者叫讀鎖（READ LOCK）和寫鎖（WRITE LOCK）。

根據(jù)粒度劃分又分表鎖和行鎖。表鎖由數(shù)據(jù)庫服務(wù)器實現(xiàn)，行鎖由存儲引擎實現(xiàn)。

除此之外,我們可以顯示加鎖

加鎖時, 如果沒有索引，會鎖表，如果加了索引，就會鎖行

InnoDB默認(rèn)支持行鎖，獲取鎖是分步的，并不是一次性獲取所有的鎖，因此在鎖競爭的時候就會出現(xiàn)死鎖的情況

解決方法:

即ACID特性:

由于并發(fā)事務(wù)會引發(fā)上面這些問題, 我們可以設(shè)置事務(wù)的隔離級別解決上面的問題.

MySQL的默認(rèn)隔離級別（可重復(fù)讀）

查看當(dāng)前會話隔離級別

方式1

方式2

設(shè)置隔離級別

主從集群的示意圖如下:

主要涉及三個線程： binlog 線程、 I/O 線程和 SQL 線程。

同步流程:

由于MySQL主從集群只會從主節(jié)點同步到從節(jié)點, 不會反過來同步, 所以需要讀寫分離

讀寫分離需要在業(yè)務(wù)層面實現(xiàn) , 寫數(shù)據(jù)只能在主節(jié)點上完成, 而讀數(shù)據(jù)可以在主節(jié)點或從節(jié)點上完成

索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)

MySQL的索引有

推薦兩個在線工具:

簡單來說, B樹是在紅黑樹(一個平衡二叉樹)的基礎(chǔ)上將一個節(jié)點存放多個值, 實現(xiàn)的, 降低了樹的高度, 每個節(jié)點都存放索引及對應(yīng)數(shù)據(jù)指針, 同一層的節(jié)點是遞增的

而B+樹在B樹的基礎(chǔ)上進(jìn)行優(yōu)化, 非葉子節(jié)點存放 子節(jié)點的開始的索引, 葉子節(jié)點存放索引和數(shù)據(jù)的指針, 且葉子節(jié)點之間有雙向的指針

如下示意圖:

不同的引擎, 主鍵索引存放的數(shù)據(jù)也不一樣, 比如常見的 MyISAM 和 InnoDB

MyISAM 的B+樹葉子節(jié)點存放表數(shù)據(jù)的指針, InnoDB 的B+樹葉子節(jié)點存放處主鍵外的數(shù)據(jù)

其他的:

即多個列組成一個索引, 語法:

由于聯(lián)合索引的B+樹的結(jié)構(gòu), 根據(jù)列建立, 所以我們的查找條件也要根據(jù)索引列的順序( where column1=x, column2=y,columnN... ), 否則會全表掃描

如果你對列進(jìn)行了 （+，-，*，/，!） , 那么都將不會走索引。

OR 引起的索引失效

OR 導(dǎo)致索引是在特定情況下的，并不是所有的 OR 都是使索引失效，如果OR連接的是 同 一個字段，那么索引 不會失效 ， 反之索引失效 。

這個我相信大家都明白，模糊搜索如果你前綴也進(jìn)行模糊搜索，那么不會走索引。

這兩種用法，也將使索引失效。另 IN 會走索引，但是當(dāng)IN的取值范圍較大時會導(dǎo)致索引失效，走全表掃描, 見: MySQL中使用IN會不會走索引

不走索引。

走索引。

所以設(shè)計表的時候, 建議不可為空, 而是將默認(rèn)值設(shè)置為 "" ( NOT NULL DEFAULT "" )

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為什么采用b+樹
分享路徑：http://www.yijiale78.com/article16/hhipdg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、ChatGPT、服務(wù)器托管、網(wǎng)站策劃、外貿(mào)網(wǎng)站建設(shè)、做網(wǎng)站

廣告

聲明：本網(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)