一、数据库索引相关概念¶

• 索引概念介绍：

索引是数据库中用来提高数据读取性能的常用工具，所有mysql列类型都可以被索引，对相关列使用索引；

可以是提高select操作性能的最佳途径，可以尽可能快的锁定要查询数据的范围，从而达到加速查询的目的（减少IO消耗）；

一般索引设置都是应用在比较大的数据表上，比如百万级别、千万级别或亿级别的数据表中，从而完成一些针对性优化；

可以简单理解：数据库索引相当于书的目录，可以借助索引有针对的查看相应数据的信息，避免了全盘检索带来的工作量；

主要利用MySQL中的索引，可以快速锁定查询范围，mysql索引比较适合范围查找数据;

二、数据库索引类型介绍¶

在MySQL数据库服务中，是有很多种索引类型的，但是比较常用的索引类型主要有：

2.1 数据库数据查找算法演变：（B+Tree索引的由来）¶

这个举个简单的例子，假设现在一个教室中有100来号人，这时可以派发礼品，通过礼品引诱这100人来报名学习xiaoQ老师课程；

比如礼品是学习课程的1000元代金券，现在把这1000元的代金券随机放到了1到100号盒子其中的一个里面，只有我知道放置的号码；

下面要求这100个人尽量快的猜到1~100号盒子里面，哪个有放置代金券的盒子，当然，我会给予一些合适的提示信息；

这时在场的100号人就需要想一些办法，在我合适的配合下，定位有代金券的盒子，想的办法就等价于是查找算法：

方法一：根据定位的盒子编号顺序，询问是与否，这种方式就可以理解为是遍历算法（全扫描），也可以理解为随机性算法；

方法二：根据定位的盒子编号比较，询问大与小，这种方式就可以理解为是二分算法（定范围），也可以理解为二叉树算法；

​ 看似这种二分算法比遍历算法，更加科学，但是如果代金券放在了第01号或第100号盒子里呢，或者二分节点两侧时呢？

​ 所以采用二分法依然会存在数据查询不平衡的问题。

通过以上两种算法的介绍，了解到都存在一些缺陷或问题，因此数据库在检索数据信息时，最终采用的算法是B+Tree，其中的B表示平衡

并且BTREE还可以细分为B-tree或B+tree，以及B++tree，其中的加号就是表示增强版或优化版的BTree；

在讲解B+树之前先了解一下树的整体结构，无非就是二叉树、二叉搜索树、平衡二叉树，更高级一点的有红黑树、Btree、B+tree等；

而树的查找性能取决于树的高度，让树尽可能平衡是为了降低树的高度。

为什么MySQL会选用B+树的结构，可以先来看看其他的树形结构：

二叉树：

二叉树的每一个节点都只有两个子节点，当需要向其插入更多的数据的时候，就必须要增加树的高度，而增加树的高度会导致IO消耗大；

对于二叉树而言，它的查找操作的时间复杂度就是树的高度，树的高度越高查询性能就会随着数据的增多越来越低。

红黑树：

红黑树一种平衡二叉树，它复杂的定义和规则都是为了保证树的平衡性；

对于B+tree算法的底层算法逻辑理解：

利用Btree算法还是快速锁定100个盒子中，有代金券的盒子编号，如下图所示：

• 将需要存储的数据信息，均匀分配保存到对应页当中，最终数据信息的均匀存储（落盘）

• 根据页节点存储的数据信息，取出页节节点最小数据信息，并将每个叶节点最小数据信息进行汇总整合，生成相应内部节点数据；

实质上存储的是下层页节点的区间范围，以及与之对应的指针信息，最后构建出内部节点信息；

• 根据内部节点存储的数据信息，取出内部节点最大数据信息，并将每个内部节点最大值信息进行汇总整合，生成相应根节点数据；

根节点只能有占用一个页区域，如果一个页区域空间不够，需要进行内部节点层次扩展，但是尽量要保证层次越少越好；

实质上存储的是下层内部节点的区域范围，以及与之对应的指针信息，最后构建出独立且唯一的根节点信息；

• 整个树形结构，越向上节点存储数据的范围越大，然后依次再分发数据到下面的小范围，最终形成多叉树；

由于出现了多叉树，就表示全部数据分布在多个链表上，避免了单条链表存储数据，同时可以实现并发的访问数据

• 对于加号表示增强，其中增强表示在整个链表上，增加了同级相邻节点之间的双向指针，从而实现相邻节点相互跳转

根据以上B+Tree的结构说明，假设现在需要查找54这个数据值信息所在的数据页：等值查询

• 根据定义查找的数值信息，首先在根节点中获取数值所在的区间范围和相应指针信息，从而找到下层对应的内部节点信息；
• 根据定义查找的数据信息，其次在枝节点中获取数值所在的区域范围和相应指针信息，从而找到下层对应的叶子节点信息；
• 根据定义查找的数据信息，最后在叶子节点中获取最终的数据信息，结果结合上图经历三步完成了数据查找（3*16=48kB）；

在利用BTree查找数据信息时，会结合树形层次结构，来决定查询数据的步骤过程，并且理论上每个数据查找过程步骤相同；

总结：B代表的平衡含义就是，每次查找数据消耗的IO数量是一致的，并且读取的页数量也是一致的，查找时间复杂度是一致的；

根据以上B+Tree的结构说明，假设现在需要查找大于90这个数据值信息所在的数据页：不等值查询

• 根据定义查找的数值信息，首先在根节点中获取首个大于指定数值的区间范围和相应指针信息，从而找到下层对应的内部节点信息；
• 根据定义查找的数据信息，其次在枝节点中获取数值所在的区域范围和相应指针信息，并且结合双向指针进行预读；
• 根据定义查找的数据信息，最后在叶子节点中获取最终的数据信息，并且结合双向指针进行预读，查询其余大于90的数值；

在利用BTree查找数据信息时，由于存在双向指针概念，可以避免重复从根查找问题，减少IO消耗，结合预读快速调取数据到内存中

总结：在BTree中的双向链接增强特性和预读功能，可以根据簇（64page）读取数据，可以使数据信息的范围查找变得更加方便高效

小结：

• 遍历方式查询数据： 逐个数据信息查询
• 二叉树方式查询数据：每个数据节点有两个分支，根据不断分支信息查询数据 查询数据效率不平衡
• BTree方式查询数据： 在进行等值数据查询时，每次查询消耗的IO数量相等 balance
• B+Tree方式查询数据：在进行等值数据/范围查询查询时，每次查询消耗的IO数量相等或者更少 + 数据页节点之间双向指针

2.2 B+Tree面试题¶

1、介绍下B+Tree索引结构？

答：

• 将需要存储的数据信息，均匀分配保存到对应页当中，最终数据信息的均匀存储（落盘）

• 根据页节点存储的数据信息，取出页节节点最小数据信息，并将每个叶节点最小数据信息进行汇总整合，生成相应内部节点数据；

实质上存储的是下层页节点的区间范围，以及与之对应的指针信息，最后构建出内部节点信息；

• 根据内部节点存储的数据信息，取出内部节点最大数据信息，并将每个内部节点最大值信息进行汇总整合，生成相应根节点数据；

根节点只能有占用一个页区域，如果一个页区域空间不够，需要进行内部节点层次扩展，但是尽量要保证层次越少越好；

实质上存储的是下层内部节点的区域范围，以及与之对应的指针信息，最后构建出独立且唯一的根节点信息；

• 整个树形结构，越向上节点存储数据的范围越大，然后依次再分发数据到下面的小范围，最终形成多叉树；

由于出现了多叉树，就表示全部数据分布在多个链表上，避免了单条链表存储数据，同时可以实现并发的访问数据

• 对于加号表示增强，其中增强表示在整个链表上，增加了同级相邻节点之间的双向指针，从而实现相邻节点相互跳转

2、利用B+Tree索引结构如何调取数据？

答：

等值查询数据：任意数据查询消耗IO相等

范围查询数据：可以尽量减少IO消耗

3、利用B+Tree索引可以在数据表中创建什么方式索引？

答：聚簇索引和辅助索引