一、数据库索引
1.1、背景
数据库索引使用树形存储结构，主要是树的查询效率高，而且可以保持有序。二叉树的查询速度和查询次数都是最小的，但是磁盘IO次数过大。
1.2、索引的查询过程
数据库索引是存储在磁盘上的，当数据量大的时候，索引的大小可能有几个G。当我们利用索引查询的时候，不会把整个索引全部加载到内存中，只能逐一加载每一个磁盘页，这里的磁盘页对应着索引树的节点。
二、B-树
2.1、定义
B-树是一种多路平衡查询树，它的每一个节点最多包含m个孩子，m被称为B树的阶。m的大小取决于索引页的大小。
2.2、特征
- 1.根结点至少有两个子女。
- 2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
- 3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
- 4.所有的叶子结点都位于同一层。
- 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
2.3、查询性能
相较于二叉树，查询次数更多，但是IO次数减少，多的只是内存交互，可以忽略。
2.4、应用
文件系统以及部分数据库索引，如非关系型数据库MongoDB。
三、B+树
3.1、定义
B+树是B-树的一种变体，有着比B-树更高的查询性能。
3.2、特征
- 1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
- 2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
- 3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
- 4.始终保持最大元素在跟节点当中。
3.3、卫星数据
所谓卫星数据，指的是索引元素所指向的数据记录，比如数据库中的某一行。
- 在B-树种，中间节点和叶子节点都带有卫星数据。
- 而在B+树中，只有叶子节点带有卫星数据，中间节点只是索引，没有任何数据关联。
3.4、聚集索引
在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。
3.5、与B-树相比优势
- 单一节点存储更多的元素：IO次数更少；
- 所有查询都要查找到叶子节点：查询性能稳定；
- 所有叶子节点形成有序链表：范围查询简单。
详解- B+树中，中间节点没有卫星数据，所以同样大小的磁盘页可以容纳更多的元素。这就意味着，数据量相同的情况下，B+树更矮胖，查询的时候IO次数更少。
- B+树查询的时候，必须要找到叶子节点，二B-树则只要匹配到元素即可，无论是中间节点还是叶子节点。因此B-树查询性能不稳定，B+树则是稳定的。
- 范围查找的实现逻辑不一样。B-树是依靠遍历，而B+树只需要在链表上做遍历即可
3.6、应用
MySQL数据库索引。
四、Mysql EXPLAIN
4.1、EXPLAIN 后type 索引扫描的方式有几种？
system > const > eq_ref > ref > range > index > ALL
一般来说，得保证查询至少达到range级别，最好能达到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、索引查询ref
EXPLAIN SELECT * from hl_info where out_id = '888889059181' and source = 2;
4.5、没用到索引是ALL或者index
-- out_id是varchar类型，这里用数字不会用到索引
-- type 索引扫描的方式（这里用到的是index）
EXPLAIN SELECT * from hl_info where out_id = 888889059181 and source = 2;
