5 算法和索引

5.1 InnoDB索引

幾種常見索引

B+樹索引

全文索引

hash索引(自適應(yīng)hash索引)

5.2 數(shù)據(jù)結(jié)構(gòu)與算法

5.2.1 二分查找

5.2.2 二叉查找樹和平衡二叉樹

B+樹是有二叉查找樹，再由平衡二叉樹(AVL)，B樹演化而來的

注意： B+樹并不能找到一個(gè)給定鍵值的具體行，能找到的只是被查找數(shù)據(jù)行所在的頁(yè)，然后數(shù)據(jù)庫(kù)講頁(yè)讀入內(nèi)存，然后內(nèi)存中進(jìn)行查找。

平衡二叉樹(AVL)樹：首先符合二叉查找書的定義，其次必須滿足任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差為1.

5.3 B+樹

5.3.1 B+樹的插入操作

B+樹插入必須保證插入后葉子節(jié)點(diǎn)中的記錄依然排序，同時(shí)需要考慮插入到B+樹的三種情況：

不管怎么變化，B+樹總是平衡的。但是為了保持平衡對(duì)于新插入的鍵值可能需要做大量的查分頁(yè)操作。因?yàn)锽+樹結(jié)構(gòu)主要用于磁盤，頁(yè)的拆分意味著磁盤操作，所以應(yīng)該在可能的情況下減少頁(yè)的拆分操作。因此B+樹也有類似于平衡二叉樹的旋轉(zhuǎn)操作。

旋轉(zhuǎn)發(fā)生在Leaf page已滿，但是其兄弟節(jié)點(diǎn)未滿的情況下，這是B+樹并不會(huì)基于拆分操作，而是將記錄轉(zhuǎn)移到頁(yè)的兄弟節(jié)點(diǎn)上。

5.3.2 B+樹的刪除操作

B+樹使用填充因子(fill factor)來控制樹的刪除變化，50%是填充因子可設(shè)置的最小值。

B+樹的刪除操作也有三種情況：

5.4 B+樹索引

B+樹在數(shù)據(jù)庫(kù)中有一個(gè)特點(diǎn)是高扇出性，因此在數(shù)據(jù)庫(kù)中，B+樹的高度一般在2_{4層，這也就是說查找某一鍵值的行記錄最多也只需要2}4次IO。

數(shù)據(jù)庫(kù)中的B+數(shù)索引可分為聚集索引(clustered index)和輔助索引(secondary index)，但是不管是哪種索引，其內(nèi)部都是B+樹，即高度平衡的，葉子節(jié)點(diǎn)中存放著所有的數(shù)據(jù)。聚集索引與輔助索引不同的是，葉子節(jié)點(diǎn)存放的是否是一整行的信息。

5.4.1 聚集索引

InnoDB存儲(chǔ)引擎表示索引組織表，即表中數(shù)據(jù)按照主鍵順序存放

聚集索引(clustered index)就是按照每張表的主鍵構(gòu)造一顆B+樹，同時(shí)葉子節(jié)點(diǎn)中存放的即為整張表的行記錄數(shù)據(jù)，也將聚集索引的葉子節(jié)點(diǎn)稱為數(shù)據(jù)頁(yè)。

由于實(shí)際的數(shù)據(jù)頁(yè)只能按照一顆B+樹進(jìn)行排序，因此每張表只能擁有一個(gè)聚集索引。

5.4.2 輔助索引

輔助索引(Secondary Index，也稱非聚集索引)，葉子節(jié)點(diǎn)并不包含記錄全部數(shù)據(jù)。葉子節(jié)點(diǎn)中除了包含鍵值以外，每個(gè)葉子節(jié)點(diǎn)的索引行中還包含了一個(gè)書簽(bookmark)。 該書簽用來告訴InnoDB引擎哪里可以找到與索引相對(duì)應(yīng)的行數(shù)據(jù)

InnoDB存儲(chǔ)引擎的輔助索引的書簽就是相應(yīng)行數(shù)據(jù)的聚集索引。(即要通過輔助索引查找數(shù)據(jù)，先找到輔助索引的葉節(jié)點(diǎn)，在根據(jù)葉節(jié)點(diǎn)中的書簽找到聚集索引的主鍵，然后再根據(jù)主鍵從聚集索引中找到葉節(jié)點(diǎn)中的行記錄)

5.4.3 B+樹索引的分裂

B+樹索引頁(yè)的分裂并不總是從頁(yè)的中間記錄開始，可能會(huì)導(dǎo)致頁(yè)空間的浪費(fèi)

5.4.4 B+樹索引的管理

索引管理

索引的創(chuàng)建和刪除兩種方法：一種是ALTER TABLE，另一種是CREATE/DROP INDEX

-- alter alter table tbl_name add [index|key] [index_name];alter table tbl_name drop primary key; --create create [unique] index index_name [index_type] on tbl_name(index_col_name);drop index index_name on tbl_name;

用戶可以設(shè)置對(duì)整個(gè)列的數(shù)據(jù)進(jìn)行索引，也可以只索引一個(gè)列的開頭部分?jǐn)?shù)據(jù)

-- 索引前邊100 alter table t add key ind_b (b(100));-- 查看索引信息 show index from tbl_name;

如;

create table t ( a varchar(1), b varchar(8000), c varchar(2),primary key a(a),key b(b(100)),key c(c),key a_c(a,c) );

上表使用show index from t， 可以觀察到表t有4個(gè)索引， 分別為a主鍵索引、c的輔助索引，b的前100字節(jié)的輔助索引，以及a、c的聯(lián)合輔助索引。show index from t可以觀察每列的含義：

Table表明

Non_unique	非唯一索引，0：表示唯一索引， 1表示非唯一索引
Key_name	索引名稱
Seq_in_index	該列在索引中的位置，聯(lián)合索引能夠觀察的區(qū)別
Column_name	該列的名稱
Collation	列以什么方式存儲(chǔ)在索引中。值可以為A或NULL，B+樹的索引總是A，即排序的
Cardinality	非常關(guān)鍵的值，表示索引中唯一值數(shù)目的估計(jì)值，該值應(yīng)該盡可能的接近1，如果非常小，需要考慮刪除該索引 (書上說盡可能接近1 實(shí)際測(cè)試mysql8.0：該值如果接近1或者遠(yuǎn)小于當(dāng)前表的數(shù)量時(shí)，應(yīng)該刪除) 例如：employee 表有30萬條數(shù)據(jù)，其中 gender(性別)只有兩種選項(xiàng)，如果給 gender 設(shè)置索引時(shí)，show table index 時(shí)，該值會(huì)接近1 (該值和總數(shù)的比值應(yīng)該接近1 ，而不是該值接近1)
Sub_part	是否是該列部分索引
Packed	關(guān)鍵值是否被壓縮
Null	是否索引的列允許NULL值
Index_type	索引類型，InnoDB引擎總是BTree
Comment	注釋

Cardinality值非常關(guān)鍵，優(yōu)化器會(huì)根據(jù)這個(gè)值來判斷是否使用這個(gè)索引。但是這個(gè)值不是實(shí)時(shí)更新的。如果需要更新的話使用命令A(yù)NALYZE TABLE命令。

Fast Index Creation

Mysql版本5.5之前，對(duì)于添加索引或刪除操作，數(shù)據(jù)庫(kù)的操作過程為：

首先創(chuàng)建一張新的臨時(shí)表，表結(jié)構(gòu)為通過命令A(yù)LTER TABLE新定義的結(jié)構(gòu)

然后把原表中的數(shù)據(jù)導(dǎo)入到臨時(shí)表

接著刪除原表

最后把臨時(shí)表重命名為原表

這種操作對(duì)于原表非常大的情況則需要很長(zhǎng)的時(shí)間。

InnoDB引擎從1.0.x版本開始支持Fast Index Creation(快速索引創(chuàng)建)的方式---FIC。對(duì)于輔助索引的創(chuàng)建，InnoDB引擎會(huì)對(duì)創(chuàng)建索引的表加上一個(gè)S鎖，在創(chuàng)建的過程中不需要重建表。

5.5 Cardinality值

5.5.1 Cardinality

? 對(duì)于什么時(shí)候添加B+樹索引，一般經(jīng)驗(yàn)是，在訪問表中很少一部分時(shí)使用B+樹索引才有意義(區(qū)分度大)，對(duì)于性別地域等不適合建立索引。如一個(gè)字段的取值范圍非常廣，幾乎沒有重復(fù)，屬于高選擇性，此時(shí)使用B+樹索引是合適的。
怎樣查看字段是否高選擇性？可以通過SHOW INDEX結(jié)果列中的Cardinality來觀察。這個(gè)值和當(dāng)前表總數(shù)的比值應(yīng)該盡可能的接近1

5.5.2 InnoDB存儲(chǔ)引擎的Cardinality統(tǒng)計(jì)

在InnoDB引擎中，Cardinality統(tǒng)計(jì)信息的更新是發(fā)生在兩個(gè)操作中：INESRT和UPDATE。

InnoDB引擎內(nèi)部更新Cardinality的側(cè)臉：

表中1/16的數(shù)據(jù)已經(jīng)發(fā)生變化

stat_modified_counter>2 000 000 000

怎樣統(tǒng)計(jì)Cardinality信息的：即采樣過程：

取得B+樹索引中葉子節(jié)點(diǎn)的數(shù)量，記為A

隨機(jī)取得B+樹索引中的8個(gè)葉子節(jié)點(diǎn)。統(tǒng)計(jì)每個(gè)頁(yè)不同記錄的個(gè)數(shù)，記為P1，P2,P3.....P8

根據(jù)采用信息給出Cardinality的預(yù)估值：Cardinality=(P1+P2+.....+P8) / 8 * A

參數(shù)：

Innodb_stats_sample_pages：采樣頁(yè)的數(shù)量，默認(rèn)為8

innodb_stats_method：默認(rèn)為 nulls_equals，視null為相等 (nulls_unequal/nulls_ignored)

以下操作會(huì)導(dǎo)致重新計(jì)算 Cardinality：

ANALYZE TABLE

SHOW TABLE STATUS

SHOW INDEX FROM

訪問 INFORMATION_SCHEMA 下的 TABLES 和 STATISTICS

5.6 B+樹索引的使用

5.6.2 聯(lián)合索引

聯(lián)合索引是指對(duì)表上的多個(gè)列進(jìn)行索引。例如

create table t (a int,b int,primary key(a),key idx_a_b(a,b) ) engine = innodb

上圖可以看到多個(gè)鍵值的B+樹，鍵值都是排序的，通過葉子節(jié)點(diǎn)可以邏輯上順序地讀出所有數(shù)據(jù)。
因此對(duì)于select * from table where a=xxx and b=xxx,是可以使用到索引的，對(duì)于select * from table where a = xxx，也是可以用到索引的，但是select * from table where b=xxx是用不到索引，因?yàn)槿~子節(jié)點(diǎn)的b值1/2/1/4/1/2，顯然不是順序排序的，因此對(duì)b列的查詢使用不到索引(a，b)的。

聯(lián)合索引的第二個(gè)好處就是已經(jīng)對(duì)第二個(gè)鍵值進(jìn)行了排序處理。

例子：

CRATE TABLE bug_log(userid int not null,buy_date date ) engine=innodb; insert into bug_log values(1, '2020-01-01'); insert into bug_log values(2, '2020-02-01'); insert into bug_log values(3, '2020-03-01'); insert into bug_log values(1, '2020-04-01'); insert into bug_log values(2, '2020-05-01'); insert into bug_log values(3, '2020-06-01');alter table bug_log add key (userid); alter table bug_log add key (userid, bug_date);

上述 sql 建立了兩個(gè)索引，當(dāng)執(zhí)行select * from bug_log where userid = 1時(shí)，優(yōu)化器會(huì)使用單個(gè)的 userid 索引，因?yàn)樵撍饕娜~子節(jié)點(diǎn)包含單個(gè)鍵值，理論上一個(gè)頁(yè)能夠存放更多的記錄

5.6.3 覆蓋索引

? InnoDB存儲(chǔ)引擎支持覆蓋索引(covering index，或索引覆蓋)，即從輔助索引中就可以得到查詢的記錄，而不需要查詢聚集索引中的記錄。使用覆蓋索引的一個(gè)好處就是輔助索引不包含整行記錄的所有信息，故其大小要遠(yuǎn)小于聚集索引，因此可以減少IO操作。

例如：

輔助索引葉子節(jié)點(diǎn)中有(primary key1, primary key2, key1, key2)以下 sql 可以使用一次輔助索引即可完成：

select key2 from table where key1 = xx; select primary key1 from table where key1 = xx; select primary key1, primary key2, key1, key2 from table where key1 = xx;

例如：一些統(tǒng)計(jì) sql

select count(*) from bug_log; -- 該 sql 并不會(huì)使用聚集索引進(jìn)行統(tǒng)計(jì)，因?yàn)閎ug_log 上有輔助索引，而輔助索引遠(yuǎn)小于聚集索引，優(yōu)化器選擇輔助索引可以減少 IO 操作

一般情況下，如(a,b)這樣的聯(lián)合索引，是不可以選擇列 b 中所謂的查詢條件，但是如果時(shí)統(tǒng)計(jì)操作，并且時(shí)覆蓋索引的，是可以使用聯(lián)合索引的，例如：

select count(*) from bug_log where bug_date > '2020-01-01' and bug_date < '2020-02-01';

5.6.4 優(yōu)化器不適用索引的情況

在某些情況下，優(yōu)化器并不會(huì)選擇使用索引，這種情況多數(shù)發(fā)生于范圍查找、join鏈接操作等情況。

select * from orderdetails where orderid > 10000 and orderid < 102000;

對(duì)于上述sql，通過命令show index from orderdetails，可以觀察到：

orderdetails表有(orderid，productid)的聯(lián)合主鍵，此外還有orderid的單個(gè)索引，上述sql顯然可以通過掃描orderid列上的索引進(jìn)行數(shù)據(jù)的查找，然而通過explain命令，實(shí)際上并沒有使用orderid上的索引來查找的

在posable_keys一列可以看到查詢可以使用PRIMARY、OrderID、OrdersOrder_details三個(gè)索引，但是時(shí)間使用的是PRIMARY聚集索引，也就是全表掃描，而非OrderID輔助索引掃描。

這個(gè)是因?yàn)橛脩暨x擇的是整行信息，而OrderID索引不能覆蓋到我們查詢的信息，因此在對(duì)OrderID索引查詢到指定數(shù)據(jù)后，還需要一次書簽訪問來查找整行數(shù)據(jù)的信息，雖然OrderID是順序存放的，但是在進(jìn)行一次書簽訪問則是無序的，變?yōu)榱穗x散讀。

5.6.5 索引提示

顯示的告訴mysql使用哪個(gè)索引：以下情況可以顯示可以顯示的告訴mysql使用哪個(gè)索引

mysql數(shù)據(jù)的優(yōu)化器錯(cuò)誤的使用了某個(gè)索引(發(fā)生的情況比較少)

某sql語(yǔ)句可以選擇的索引非常多，優(yōu)化器選擇執(zhí)行計(jì)劃的開銷可能大于sql語(yǔ)句本身。

例子：

select * from tbl_name force index(a) where ***

5.6.6 Multi-Range Read 優(yōu)化

mysql5.6版本開始支持Multi-Range Read(MRR)優(yōu)化，MRR優(yōu)化的目的就是為了減少磁盤的隨機(jī)訪問，并接將隨機(jī)訪問轉(zhuǎn)化為順序地?cái)?shù)據(jù)訪問，這對(duì)于IO-bound類型的sql查詢的性能帶來極大的提升。

MRR優(yōu)化可適用于range，ref，eq_ref類型的查詢：

MRR優(yōu)化好處：

使數(shù)據(jù)訪問變得較為順序。在查詢輔助索引時(shí)，首先根據(jù)得到的查詢結(jié)果，按照主鍵進(jìn)行排序，并按照主鍵排序進(jìn)行書簽查找

減少緩沖池中頁(yè)被替換的次數(shù)

批量處理對(duì)鍵值的查詢操作

在進(jìn)行某些范圍查詢時(shí)，講范圍值拆分為鍵值對(duì)，以此來批量查詢

是否啟用MRR優(yōu)化可以設(shè)置參數(shù)optimizer_switch中的標(biāo)記(flag)來控制。當(dāng)mrr為on時(shí)，表示啟用。mrr_const_based標(biāo)記設(shè)置off，則總是啟用mrr優(yōu)化。

set @@optimizer_switch='mrr=on,mrr_cost_based=off';

5.6.7 Index Condition Pushdown(ICP)優(yōu)化

該優(yōu)化也是在mysql5.6開始支持的一種優(yōu)化方式。

在不支持ICP之前，當(dāng)進(jìn)行查詢操作時(shí)，首先根據(jù)索引查找記錄，然后再根據(jù)where條件進(jìn)行過濾。

支持ICP之后，mysql數(shù)據(jù)庫(kù)會(huì)在取出索引的同時(shí)，判斷是否可以進(jìn)行where條件的過濾，也就是將where的部分過濾操作放在了存儲(chǔ)引擎層。在某些查詢下，可以大大減少對(duì)記錄的獲取。

可支持的類型：range、ref、eq_ref、ref_or_null。

5.7 哈希算法

5.7.1 哈希表

又稱離散表。哈希表由直接尋址表改進(jìn)而來的

5.7.2 InnoDB存儲(chǔ)引擎中的哈希算法

InnoDB引擎使用哈希算法來對(duì)字典進(jìn)行查找，起沖突機(jī)制采用鏈表方式，hash函數(shù)采用除法散列方式。

在緩沖池中的page頁(yè)都有一個(gè)chain指針，它指向相同hash函數(shù)值得頁(yè)。對(duì)于除法散列，m的取值為略大于2倍的緩沖池頁(yè)數(shù)量的質(zhì)數(shù)。

例如：當(dāng)前參數(shù)innodb_buffer_pool_size的大小為10M，則共用640個(gè)16kb的頁(yè)，對(duì)于緩沖池內(nèi)存的hash表來說，需要分配640*2=1280個(gè)槽，但是由于1280不是質(zhì)數(shù)，則取略大的質(zhì)數(shù)1399.

5.8 全文檢索

總結(jié)

以上是生活随笔為你收集整理的mysql ---- innodb-2-索引的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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