一、數(shù)據(jù)庫(kù)索引
1.1遏弱、背景
數(shù)據(jù)庫(kù)索引使用樹形存儲(chǔ)結(jié)構(gòu)盆均，主要是樹的查詢效率高，而且可以保持有序漱逸。二叉樹的查詢速度和查詢次數(shù)都是最小的泪姨，但是磁盤IO次數(shù)過(guò)大。
1.2饰抒、索引的查詢過(guò)程
數(shù)據(jù)庫(kù)索引是存儲(chǔ)在磁盤上的肮砾，當(dāng)數(shù)據(jù)量大的時(shí)候，索引的大小可能有幾個(gè)G袋坑。當(dāng)我們利用索引查詢的時(shí)候仗处，不會(huì)把整個(gè)索引全部加載到內(nèi)存中，只能逐一加載每一個(gè)磁盤頁(yè)枣宫，這里的磁盤頁(yè)對(duì)應(yīng)著索引樹的節(jié)點(diǎn)甥啄。
二山叮、B-樹
2.1孝冒、定義
B-樹是一種多路平衡查詢樹碳却，它的每一個(gè)節(jié)點(diǎn)最多包含m個(gè)孩子，m被稱為B樹的階翅娶。m的大小取決于索引頁(yè)的大小文留。
2.2好唯、特征
- 1.根結(jié)點(diǎn)至少有兩個(gè)子女。
- 2.每個(gè)中間節(jié)點(diǎn)都包含k-1個(gè)元素和k個(gè)孩子燥翅，其中 m/2 <= k <= m
- 3.每一個(gè)葉子節(jié)點(diǎn)都包含k-1個(gè)元素渠啊，其中 m/2 <= k <= m
- 4.所有的葉子結(jié)點(diǎn)都位于同一層。
- 5.每個(gè)節(jié)點(diǎn)中的元素從小到大排列权旷，節(jié)點(diǎn)當(dāng)中k-1個(gè)元素正好是k個(gè)孩子包含的元素的值域分劃替蛉。
2.3、查詢性能
相較于二叉樹拄氯，查詢次數(shù)更多躲查，但是IO次數(shù)減少，多的只是內(nèi)存交互译柏，可以忽略镣煮。
2.4、應(yīng)用
文件系統(tǒng)以及部分?jǐn)?shù)據(jù)庫(kù)索引鄙麦，如非關(guān)系型數(shù)據(jù)庫(kù)MongoDB典唇。
三胯府、B+樹
3.1介衔、定義
B+樹是B-樹的一種變體，有著比B-樹更高的查詢性能骂因。
3.2炎咖、特征
- 1.有k個(gè)子樹的中間節(jié)點(diǎn)包含有k個(gè)元素（B樹中是k-1個(gè)元素），每個(gè)元素不保存數(shù)據(jù)寒波，只用來(lái)索引乘盼，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。
- 2.所有的葉子結(jié)點(diǎn)中包含了全部元素的信息俄烁，及指向含這些元素記錄的指針绸栅，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
- 3.所有的中間節(jié)點(diǎn)元素都同時(shí)存在于子節(jié)點(diǎn)页屠，在子節(jié)點(diǎn)元素中是最大（或最写饪琛）元素。
- 4.始終保持最大元素在跟節(jié)點(diǎn)當(dāng)中卷中。
3.3矛双、衛(wèi)星數(shù)據(jù)
所謂衛(wèi)星數(shù)據(jù)渊抽，指的是索引元素所指向的數(shù)據(jù)記錄蟆豫，比如數(shù)據(jù)庫(kù)中的某一行。
- 在B-樹種懒闷，中間節(jié)點(diǎn)和葉子節(jié)點(diǎn)都帶有衛(wèi)星數(shù)據(jù)十减。
- 而在B+樹中栈幸，只有葉子節(jié)點(diǎn)帶有衛(wèi)星數(shù)據(jù)，中間節(jié)點(diǎn)只是索引帮辟，沒(méi)有任何數(shù)據(jù)關(guān)聯(lián)速址。
3.4、聚集索引
在數(shù)據(jù)庫(kù)的聚集索引（Clustered Index）中由驹，葉子節(jié)點(diǎn)直接包含衛(wèi)星數(shù)據(jù)芍锚。在非聚集索引（NonClustered Index）中，葉子節(jié)點(diǎn)帶有指向衛(wèi)星數(shù)據(jù)的指針蔓榄。
3.5并炮、與B-樹相比優(yōu)勢(shì)
- 單一節(jié)點(diǎn)存儲(chǔ)更多的元素：IO次數(shù)更少；
- 所有查詢都要查找到葉子節(jié)點(diǎn)：查詢性能穩(wěn)定甥郑；
- 所有葉子節(jié)點(diǎn)形成有序鏈表：范圍查詢簡(jiǎn)單逃魄。
詳解- B+樹中，中間節(jié)點(diǎn)沒(méi)有衛(wèi)星數(shù)據(jù)澜搅，所以同樣大小的磁盤頁(yè)可以容納更多的元素伍俘。這就意味著，數(shù)據(jù)量相同的情況下勉躺，B+樹更矮胖癌瘾，查詢的時(shí)候IO次數(shù)更少。
- B+樹查詢的時(shí)候饵溅，必須要找到葉子節(jié)點(diǎn)柳弄，二B-樹則只要匹配到元素即可，無(wú)論是中間節(jié)點(diǎn)還是葉子節(jié)點(diǎn)概说。因此B-樹查詢性能不穩(wěn)定碧注，B+樹則是穩(wěn)定的。
- 范圍查找的實(shí)現(xiàn)邏輯不一樣糖赔。B-樹是依靠遍歷萍丐，而B+樹只需要在鏈表上做遍歷即可
3.6、應(yīng)用
MySQL數(shù)據(jù)庫(kù)索引放典。
四、Mysql EXPLAIN
4.1奋构、EXPLAIN 后type 索引掃描的方式有幾種壳影？
system > const > eq_ref > ref > range > index > ALL
一般來(lái)說(shuō)，得保證查詢至少達(dá)到range級(jí)別弥臼，最好能達(dá)到ref
4.2宴咧、主鍵查詢是const
EXPLAIN SELECT * from hl_info where id = 62678;
4.3、主鍵范圍查詢是range
EXPLAIN SELECT * from hl_info where id in(77,88);
4.4径缅、索引查詢r(jià)ef
EXPLAIN SELECT * from hl_info where out_id = '888889059181' and source = 2;
4.5掺栅、沒(méi)用到索引是ALL或者index
-- out_id是varchar類型烙肺，這里用數(shù)字不會(huì)用到索引
-- type 索引掃描的方式（這里用到的是index）
EXPLAIN SELECT * from hl_info where out_id = 888889059181 and source = 2;
