您好,登錄后才能下訂單哦!
B+tree是由二叉樹(shù)》平衡二叉樹(shù)》B-tree演化而來(lái)。
二叉樹(shù)每個(gè)節(jié)點(diǎn)最多兩個(gè)子節(jié)點(diǎn),左子樹(shù)鍵值永遠(yuǎn)小于右子樹(shù),并小于根鍵值。
平衡二叉樹(shù)在二叉樹(shù)結(jié)構(gòu)基礎(chǔ)上提高,必須滿(mǎn)足左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1,且左子樹(shù)和右子樹(shù)都是一顆平衡二叉樹(shù),,隨時(shí)要保證插入后的整棵二叉樹(shù)是平衡的,通郭左旋或右旋使不平衡的樹(shù)變平衡。
B-tree又稱(chēng)Btree,每個(gè)節(jié)點(diǎn)最多4個(gè)子節(jié)點(diǎn),除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn),其他節(jié)點(diǎn)最少2個(gè)子節(jié)點(diǎn)。所有葉子節(jié)點(diǎn)在同一層,葉子節(jié)點(diǎn)不包括任何關(guān)鍵字信息。
B+tree使Btree的變體,是一種多路搜索樹(shù),所有關(guān)鍵字和數(shù)據(jù)都保存在葉子節(jié)點(diǎn)中,并且包含關(guān)鍵字記錄的指針。
總結(jié):B+tree索引是雙向鏈表結(jié)構(gòu),檢索比B-tree快,訪(fǎng)問(wèn)關(guān)鍵字的順序是連續(xù)性的,不用再訪(fǎng)問(wèn)上一個(gè)節(jié)點(diǎn),且葉子節(jié)點(diǎn)包含所有的數(shù)據(jù)信息。
B+tree分為兩大類(lèi),一類(lèi)叫聚集索引,一類(lèi)叫非聚集索引(普通索引)。
InnoDB存儲(chǔ)引擎是索引組織表,聚集索引是一種索引組織表形式,索引鍵值的邏輯順序決定了表數(shù)據(jù)行的物理存儲(chǔ)順序。
聚集索引葉子節(jié)點(diǎn)存放表中所有行數(shù)據(jù)記錄的信息,即數(shù)據(jù)即索引、索引即數(shù)據(jù)。創(chuàng)建表時(shí)建主鍵(聚集索引),如不建主鍵則InnoDB會(huì)選擇第一個(gè)不包含由Null值得唯一索引作為主鍵,如果唯一索引沒(méi)有,則默認(rèn)為該表生成一個(gè)6字節(jié)得rowid為主鍵。
普通索引在葉子節(jié)點(diǎn)不包含所有行得數(shù)據(jù)記錄,只在葉子節(jié)點(diǎn)存有自己本身鍵值和主鍵得值。檢索數(shù)據(jù),通過(guò)普通索引葉子節(jié)點(diǎn)上主鍵來(lái)獲取想要查找的行數(shù)據(jù)記錄。
普通索創(chuàng)建語(yǔ)法:
alter table tab_name add index index_name(col1);
或:
create index inde_name on tab_name(col1);
查看表中有哪些索引;
show index from tab_name;
索引創(chuàng)建實(shí)驗(yàn)
l 創(chuàng)建測(cè)試庫(kù)
mysql> create database test;
l 創(chuàng)建測(cè)試表
DROP TABLE IF EXISTS `t`;
CREATE TABLE `t` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(20) NOT NULL,
`address` varchar(20) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
l 查看表結(jié)構(gòu)
[test]>desc t;
+---------+-------------+------+-----+---------+----------------+
| Field | Type | Null | Key | Default | Extra |
+---------+-------------+------+-----+---------+----------------+
| id | int(11) | NO | PRI | NULL | auto_increment |
| name | varchar(20) | NO | | NULL | |
| address | varchar(20) | NO | | NULL | |
+---------+-------------+------+-----+---------+----------------+
l 創(chuàng)建存儲(chǔ)過(guò)程
DELIMITER $$
DROP PROCEDURE IF EXISTS `proc_auto_insertdata`$$
CREATE PROCEDURE `proc_auto_insertdata`()
BEGIN
DECLARE init_data INTEGER DEFAULT 1;
WHILE init_data <= 60000 DO
INSERT INTO test.t VALUES(CONCAT('name', init_data), init_data + 10);
SET init_data = init_data + 1;
END WHILE;
END$$
DELIMITER ;
l 調(diào)用存儲(chǔ)過(guò)程插入數(shù)據(jù)
CALL proc_auto_insertdata();
數(shù)據(jù)插入完成,看數(shù)據(jù)文件10M
l 查看執(zhí)行計(jì)劃
test> explain select * from t where name='name11';
l 創(chuàng)建索引
create index idx_tname on t(name);
l 再次查看執(zhí)行計(jì)劃
優(yōu)化方法
l 執(zhí)行計(jì)劃查看方法:
1. 看查詢(xún)類(lèi)型type,如出現(xiàn)all,代表全表掃描;
2. 看key列,看是否使用l 索引。null表示沒(méi)有使用索引;
3. 看rows列,SQL執(zhí)行過(guò)程中被掃描的行數(shù);
4. 看extra列,觀(guān)察是否有Using filesort或Using temporary,這些影響性能。
5. 看filtered列,(5.7增加,5.6用explain extended增加此列),代表返回結(jié)果的行占需要讀取行的百分比。
l SQL優(yōu)化思路:
1. 查看表的數(shù)據(jù)類(lèi)型是否設(shè)計(jì)的合理,是否遵守選區(qū)數(shù)據(jù)類(lèi)型越簡(jiǎn)單越小的原則。
2. 表中碎片是否整理。
3. 表的統(tǒng)計(jì)信息是否收集。
4. 查看執(zhí)行計(jì)劃如沒(méi)用到索引,需創(chuàng)建。
5. 創(chuàng)建索引前,查看索引的選擇性,判斷字段是否合適創(chuàng)建索引。選擇性指不重復(fù)的索引值(基數(shù),cardinality)和記錄總數(shù)的比值,比值越高越好。
6. 創(chuàng)建索引后,再看執(zhí)行計(jì)劃,比對(duì)前后。
l 合理創(chuàng)建索引:
1. 經(jīng)常被查詢(xún)的列。
2. 經(jīng)常用于表連接的列。
3. 經(jīng)常排序分組的類(lèi)。
ICP(Index Condition Pushdown) 是mysql使用索引從表重檢索行數(shù)據(jù)的一種優(yōu)化方式。5.6開(kāi)始支持。之前存儲(chǔ)引擎取所有數(shù)據(jù)給server使用索引過(guò)濾處理。使用ICP之后,可以使用索引的話(huà),存儲(chǔ)引擎過(guò)濾完數(shù)據(jù)再給server層。ICP能減少引擎層訪(fǎng)問(wèn)基表的次數(shù)和server層訪(fǎng)問(wèn)存儲(chǔ)引擎的次數(shù)。
通過(guò)optimizer_switch參數(shù)中的index_condition_pushdow來(lái)控制,默認(rèn)開(kāi)啟。
[mysql]>show variables like '%pushdown%';
關(guān)閉:
set optimizer_switch=”index_condition_pushdown=on|off”;
使用ICP優(yōu)化時(shí),執(zhí)行計(jì)劃extra列會(huì)顯示Using index condition。
5.7中optimizer_switch參數(shù)默認(rèn)值:
|index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=on,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,duplicateweedout=on,subquery_materialization_cost_based=on,use_index_extensions=on,condition_fanout_filter=on,derived_merge=on |
MBR(Multi-Range Read Optimization) ,5.6后增加。通過(guò)optimizer_switch參數(shù)中兩個(gè)選項(xiàng)控制,參數(shù)默認(rèn)開(kāi)啟。
mrr_cost_basd:通過(guò)基于成本的算法來(lái)確定開(kāi)啟mrr特性,on自動(dòng),off強(qiáng)制開(kāi)啟。
MBR作用:把普通索引上的葉子節(jié)點(diǎn)上找到的主鍵值的集合存儲(chǔ)到read_rnd_buffer中,然后再該buffer中對(duì)主鍵值排序,然后用排序號(hào)的主鍵值集合去訪(fǎng)問(wèn)表中的數(shù)據(jù),將隨機(jī)IO編程順序IO,降低查詢(xún)過(guò)程IO開(kāi)銷(xiāo)。
使用MBR優(yōu)化時(shí),執(zhí)行計(jì)劃extra列會(huì)顯示Using MBR。
BKA(Batched Key Access),提高表join性能的算法,作用是讀取被join表的記錄時(shí)候使用順序IO。
BKA原理:多表join語(yǔ)句,使用索引訪(fǎng)問(wèn)第二個(gè)join表時(shí),使用一個(gè)join buffer來(lái)收集第一個(gè)操作對(duì)象生成的相關(guān)列值,BKA構(gòu)建好key后,批量傳給引擎層做索引查找,key通過(guò)MBR接口提交給引擎。
通過(guò)optimizer_switch參數(shù)的batched_key_access選項(xiàng)控制,默認(rèn)關(guān)閉。
要開(kāi)啟該參數(shù),必須強(qiáng)制使用MBR才行。
SET global optimizer_switch=’mrr=on,mrr_cost_based=off’;
SET global optimizer_switch=’batched_key_access=on’;
當(dāng)BKA使用時(shí),執(zhí)行計(jì)劃extra列會(huì)顯示Using join buffer(Batched Key Access)。
主鍵索引就是聚集索引,每表只能有一個(gè)。必須滿(mǎn)足三個(gè)條件:
l 主鍵值必須唯一。
l 不能包含null值。
l 一定要保證該值是自增屬性??梢员WC寫(xiě)入數(shù)據(jù)的順序也是自增的,提高存取效率。
創(chuàng)建主鍵語(yǔ)法:
alter table tab_name add primary key(col);
唯一索引,不允許有重復(fù)值,但允許空值,可以有多個(gè)唯一索引。
語(yǔ)法:
alter table tab_name add unique(col);
數(shù)據(jù)在索引中,查到索引不必再回表查詢(xún)數(shù)據(jù)。執(zhí)行計(jì)劃extra列中會(huì)出現(xiàn)Using index。
如使用覆蓋索引,一定要讓select列出所需要的列,堅(jiān)決不能直接寫(xiě)出select *
對(duì)于BLOB、TEXT或很長(zhǎng)的varchar類(lèi)型的列,為他們前幾個(gè)字符建立的索引,就是前綴索引。不能再ORDER BY 或GROUP BY中使用前綴索引,也不能用作覆蓋索引。
alter table tab_name add key(col_name(prefix_length));
注意:最關(guān)鍵的參數(shù)prefix_length,這個(gè)值需要根據(jù)實(shí)際表的內(nèi)容來(lái)得到合適的索引選擇性。
聯(lián)合索引又叫復(fù)合索引,是表中兩個(gè)或兩個(gè)以上的列創(chuàng)建的索引。
create index idx_c1_c2 on t(c1,c2);
選擇性高的列放前面。
哈希索引采用哈希算法,把鍵值換算成新的哈希值。哈希索引只能進(jìn)行等值查詢(xún),不能進(jìn)行排序、模糊查找、范圍查詢(xún)等。檢索時(shí)不需要像B+tree那樣從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)逐級(jí)查找,只需一次哈希算法即可立即定位到相應(yīng)的位置。
索引優(yōu)點(diǎn)
l 提高數(shù)據(jù)檢索效率
l 提高據(jù)合函數(shù)效率
l 提高排序效率
l 使用覆蓋索引可以避免回表
索引創(chuàng)建四個(gè)不要
l 選擇性低的字段不要?jiǎng)?chuàng)建索引
l 很少查詢(xún)的列不要?jiǎng)?chuàng)建索引
l 大數(shù)據(jù)類(lèi)型字段不要?jiǎng)?chuàng)建索引
l 盡量避免不要使用NULL,應(yīng)指定列為NOT NULL。
使用不到索引的情況
l 通過(guò)索引掃描的行記錄數(shù)超過(guò)全表30%,優(yōu)化器不會(huì)走索引,而走全表掃描。
l 聯(lián)合索引中,第一個(gè)查詢(xún)條件不是最左側(cè)列。
l 聯(lián)合索引中,第一個(gè)索引列使用范圍查詢(xún),只能使用到部分索引,有ICP出現(xiàn)。
l 聯(lián)合索引中,第一個(gè)查詢(xún)條件不是最左前綴列。
l 模糊查詢(xún)條件列最左以通配符%開(kāi)始。
l 兩個(gè)單列索引,一個(gè)用于檢索,一個(gè)用戶(hù)排序。只能使用到一個(gè)索引,因?yàn)椴樵?xún)語(yǔ)句最多只能使用一個(gè)索引,考慮建立聯(lián)合索引。
l 查詢(xún)字段上有索引,但使用了函數(shù)運(yùn)算。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。