vlambda博客
学习文章列表

基于key、value数据结构可分为hashmap、二叉树、二叉平衡树、红黑树、B树、B+树，下面粗略介绍各种数据结构的特点，从而分析为为什么MYSQL选择B+数作为索引的数据结构。

• HasMap： 散列表，内部通过数组+链表实现，插入数据时通过计算 key的hash值与数组大小取模或者位运算，获得在数组中的下标，如果出现hash冲突就采用链表或者红黑树的方式解决。在散列非常均匀的情况下，通过精确key获取value很快，时间复杂度可达到O(1)。可以发现 hashmap读hash函数的要求很高，不然不出现散列不均匀，从而转化成链表或红黑树，导致查询时间复杂度降低为O(n)或者O(logN)；并且它的数据不能持久化到磁盘，只能在内存中，如果数据量大的话，内存难以承载。还有一点它不支持高效的范围查找，只有通过精确值查找时速度很快，范围查找时，需要遍历比对。因此hashmap不适合做MYSQL的索引数据结构。
• 二叉查找树： 二叉树是一个树形结构数据结构，节点的左子节点值总是小于自身值，右子节点总是大于自身值，可以发现如果插入一组有序数据，它会变得特别长，类似一个链表，这样会导致查询效率很低，因此二叉查找树不适合做MYSQL索引。

• 二叉平衡树：为了解决二叉查找树带来的问题，二叉平衡树在插入的树节点后，对树进行多次旋转，以让树达到左右平衡，它要求最短子树和最长子树之间的差值不能超过1。这个看着貌似可以解决不平衡的问题，但是它有一个问题就是插入效率太低，插入一个节点需要进行多次树的旋转，节点移动操作，如果业务中有大量的数据插操作，效率会很低。因此它也不适合做MYSQL索引的数据结构。
  

• 红黑树： 为了解决插入效率低的问题，红黑树出现了，它不再要求树的高度之差为1，而是要求最长子树的高度不超多最短子树的2倍即可，并且把树的节点分为红色节点和黑色节点，规定任何一个路径里所有的黑色节点必须一致，一个路径中不能连续有两个红色节点。可以发现树的分叉太少，导致随着数据的增多树的高度之差会不断增大，查询效率会逐渐降低，如果能把树的分叉增多，高度之差就没那么大了。

• B树：为了解决树的高度之差和平衡性的问题，B数出现了，它不再限制树的分叉限制，一个节点可以有多个子节点，叶子结点从左到右是从大到小排列的，可以支持范围查找，并且一个树节点可以存储多条数据，允许将索引和一行data记录都放在一个树节点中，可以灵活设置一个节点包含的最大子节点数量，通常叫阶，用m表示，也可称为m叉树，一个节点中最大的元素数量为m-1，以此来控制树的高度，就是一个节点横向存储的数据越多，节点的高度就越低。由于节点中存储key，同时包含data，而每个节点的存储空间是有限的，如果data比较大的话，会导致每个节点中存储的key减少，从而会导致树的深度较大，进而影响查询性能。

• B+树：是对B树的一个优化，他在非叶子节点中只存储key，不存储data，叶子节点中存储key+data，从而在节点中存储更多的key，降低树的高度，并且将所有的树节点都按照顺序排列在叶子节点上，相邻叶子节点之间相互连接，头尾相接，形成一个环形的有序双向链表。

二、MYSQL中的B+树实现

在B+树中有两个头指针，一个指向根节点，一个指向最小的叶子节点。所有叶子节点是一个环形的有序链式结构，因此可以对B+Tree进行两种查找，

• 对于主键的范围查找和分页查找

• 从根节点开始，进行随机查找

最左匹配原则是应用在组合索引中，组合索引就是多个数据列联合索引，比如对表person中（name，age）创建联合索引，最左匹配原则就是在查询时先匹配name字段，再匹配age字段，顺序不能颠倒。构建B+Tree索引时的排列顺序也是先根据name字段做排序，如果name字段相同，再根据age字段排序。组合索引的存储结构如下图：

• 先对两张表做关联，再取出要查询的字段值

• 先将要查询的字段都查询出来，然后再根据关系字段做关联

上面两种方式第二种的效率更高，这就叫做谓词下推。

通过explain命令来分析SQL的执行过程，看有没有需要优化的地方，来提高SQL的执行效率。执行explain，可以获得以下执行计划中的信息，如下图：

• 如果ID相同，则顺序从上到下

• 如果ID不同，若是子查询，ID号会递增，ID值越大，优先级越高，越先被执行

• 如果ID有相同也有不同的，相同可以认为是一组，可以顺序往下执行，在所有组中，ID值越大，优先级越高，越先被执行
  

3) table

对应访问哪一张表，可能是真实的表名、别名或者union合并结果集

• 如果是表名或者别名，则表示是从真实的表中获取数据。
  

• 如果是derivedN，则表示使用id为N的查询产生的派生表
  

• 当有union result时，表名是union  n1,n2这种形式，n1和n2表示参与union的ID
  

‍

各种类型的值：

4.2 优化思路

•  schema与数据类型优化

•  数据类型优化

•  主键选择

•  使用范式和反范式

•  数据冗余

•  存储引擎选择