1酗电、思考??問(wèn)題為什么要使用索引？
- 索引能極大的減少存儲(chǔ)引擎需要掃描的數(shù)據(jù)量内列。
- 索引可以把隨機(jī)IO變成順序IO撵术。
- 索引可以幫助我們?cè)谶M(jìn)行分組、排序等操作時(shí)话瞧，避免使
用臨時(shí)表嫩与。
2、思考??問(wèn)題索引的底層數(shù)據(jù)結(jié)構(gòu)有哪些交排，優(yōu)缺點(diǎn)是什么划滋？
索引常用的數(shù)據(jù)結(jié)構(gòu)有：
1、hash結(jié)構(gòu)埃篓。
2古毛、B+Tree結(jié)構(gòu)。
| 索引結(jié)構(gòu) | 優(yōu)點(diǎn) | 缺點(diǎn) |
|---|---|---|
| hash結(jié)構(gòu) | 數(shù)據(jù)量小時(shí)等值查詢效率高 | 1都许、索引無(wú)法完成排序。 2嫂冻、無(wú)法區(qū)間查詢胶征。 3、無(wú)法利用部分索引 桨仿。 4睛低、大量Hash值沖突，性能無(wú)法保證。 |
| B+Tree結(jié)構(gòu) | 1钱雷、減少掃描的數(shù)據(jù)量骂铁。 2、把隨機(jī)IO變成了順序IO罩抗。 3拉庵、hash的缺點(diǎn) |
占用物理空間 |
3、思考??為什么是B+Tree套蒂？
Tree的數(shù)據(jù)結(jié)構(gòu)：
1钞支、二叉查找樹：（Binary Search Tree）
缺點(diǎn)：樹的高度沒(méi)有約束，導(dǎo)致查詢效率時(shí)間復(fù)雜度較高O(n)操刀。
2烁挟、平衡二叉樹（AVL樹）：（Balance Binary Search Tree）
缺點(diǎn)：改善了查詢的復(fù)雜度問(wèn)題（約束了左右子樹相差高度不能大于1），但是樹的高度==IO次數(shù)骨坑，即使左右子樹拉平了撼嗓，但是高度帶來(lái)的IO問(wèn)題依然無(wú)法接收，而且每塊磁盤塊（節(jié)點(diǎn)/頁(yè)）太小欢唾，沒(méi)有利用好IO數(shù)據(jù)交換特性且警。
3、B-Tree結(jié)構(gòu)（多路平衡樹）：
缺點(diǎn)：
一顆 m 階B-tree的定義：一個(gè)節(jié)點(diǎn)最多有 n 個(gè)key(關(guān)鍵字)匈辱，那么這個(gè)節(jié)點(diǎn)最多就會(huì)有 n+1 個(gè)子節(jié)點(diǎn)振湾，這棵樹就叫做 n+1（m=n+1）階樹。（個(gè)節(jié)點(diǎn)能擁有的最大子節(jié)點(diǎn)數(shù)來(lái)表示這顆樹的階數(shù)）
一棵m階的B-Tree有如下特性：關(guān)鍵字(n)亡脸， 路/階(m)押搪，度()
1. 每個(gè)節(jié)點(diǎn)最多有m個(gè)子節(jié)點(diǎn)。
2. 除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外浅碾，其它每個(gè)節(jié)點(diǎn)至少有Ceil(m/2)個(gè)孩子大州。
3. 若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則至少有2個(gè)孩子垂谢。
4. 所有葉子節(jié)點(diǎn)都在同一層厦画，且不包含其它關(guān)鍵字信息。
5. 關(guān)鍵字的個(gè)數(shù)n滿足：ceil(m/2)-1 <= n <= m-1
6. ki(i=1,…n)為關(guān)鍵字滥朱，且關(guān)鍵字升序排序根暑。
7. Pi(i=1,…n)為指向子樹根節(jié)點(diǎn)的指針。P(i-1)指向的子樹的所有節(jié)點(diǎn)關(guān)鍵字均小于ki徙邻，但都大于k(i-1)
8. 每個(gè)非終端節(jié)點(diǎn)包含n個(gè)關(guān)鍵字信息（P0,P1,…Pn, k1,…kn）
階(m)：P1排嫌、P2、P3
關(guān)鍵字(n)：n<=m-1
高度：xx
如圖：階=3缰犁，關(guān)鍵字=2淳地。
mysql默認(rèn)最小的磁盤塊空間大胁篮：16k，int 類型的id作為關(guān)鍵字大衅南蟆：4byte+4byte伍伤。所以關(guān)鍵字個(gè)數(shù)=磁盤塊空間/id：
關(guān)鍵字最多個(gè)數(shù)=(16*1024)/(4+4)=2048個(gè)，那么度<=路<=2048+1=2049遣钳。(盡量通過(guò)增加路來(lái)降低高度)
查看mysql頁(yè)的數(shù)據(jù)大腥呕辍：show variables like 'innodb_page_size';
4、B+Tree結(jié)構(gòu)：
缺點(diǎn)：
B+Tree與B-Tree區(qū)別：
1耍贾，B+節(jié)點(diǎn)關(guān)鍵字搜索采用閉合區(qū)間阅爽。
2，B+非葉節(jié)點(diǎn)不保存數(shù)據(jù)相關(guān)信息荐开，只保存關(guān)鍵字和子節(jié)點(diǎn)的引用付翁。
3，B+關(guān)鍵字對(duì)應(yīng)的數(shù)據(jù)保存在葉子節(jié)點(diǎn)中晃听。
4百侧，B+葉子節(jié)點(diǎn)是順序排列的，并且相鄰節(jié)點(diǎn)具有順序引用的關(guān)系能扒。
B+Tree優(yōu)勢(shì)：
B+樹是B-樹的變種（PLUS版）多路絕對(duì)平衡查找樹佣渴，他擁有B-樹的優(yōu)勢(shì)。
B+樹掃庫(kù)初斑、表能力更強(qiáng)辛润。
B+樹的磁盤讀寫能力更強(qiáng)。
B+樹的排序能力更強(qiáng)见秤。
B+樹的查詢效率更加穩(wěn)定（仁者見仁砂竖、智者見智）。
