MySQL索引底层数据结构与算法

B树和B+树的区别？

B+树和B树相比，主要的不同点在以下3项：

• 所有关键码都存放在叶节点中，上层的非叶节点的关键码是其子树中最小（或最大）关键码的复写
• 叶节点包含了全部关键码及指向相应数据记录存放地址的指针，且叶节点本身按关键码从小到大顺序连接。如果按下层结点“最小关键码复写”原则，则树中每个非叶结点中有 m 棵子树必有 m - 1 个关键码；如果按下层结点“最大关键码复写”原则，则树中每个非叶结点中有 m 棵子树必有 m 个关键码
• 在搜索过程中，如果查询和内部节点的关键字一致，那么搜索过程不停止，而是继续向下搜索这个分支。
   

为什么MySQL数据库索引表要选择使用B+树？ 

1、B+树的磁盘读写代价更低 

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。

2、B+树的查询效率更加稳定 

由于内部结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3、B+树更有利于对数据库的扫描 

B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的range query，B+树有着更高的性
 

什么叫聚集索引？

即叶子节点上有整行的信息。

为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？

因为Ibd文件是必须要用一颗B+树来组织，如果没有建立主键，InnoDB会选择第一个创建的非空唯一列作为主键，如果没有，则创建一个隐藏列rowId来作为主键，这样子做就会消耗MySQL的资源。

查找元素的过程中其实是经历过多次的数据比大小，相比于整型，类似于UUID的数据比较数据会很久；除此之外，整型的占用的空间更小，节省了宝贵了磁盘存储资源。

为什么要使用自增的主键（关键点自增）

如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置；此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

hash索引

哈希索引只需要对索引的key进行一次哈希计算就可以定位出数据存储的位置，所以很多时候hash索引的效率会比B+高。但是hash索引仅能满足“=”，“IN”，不支持范围查询，以及会存在hash冲突问题。而B+树通过叶子节点之间的双向指针就可以做到范围查询（B树叶子节点没有双向指针）。

 主键索引的劣势是什么？

对于高并发工作负载，在InnoDB中按主键顺序插入可能会造成明显的争用。主键上界会成为”热点”，因为所有的插入都发生在这里，所以并发插入可能导致间隙锁竞争。另一个热点可能是AUTO_INCREMENT锁机制：如果遇到这个问题，则可能需要考虑重新设计表或者应用，或者更改innodb_autoinc_lock_mode配置。

聚集索引与非聚集索引哪个查找速度快？

聚集索引会更快，对于非聚集索引要跨文件查询，聚集索引可以直接拿到数据。 

InnoDB的非主键索引

非主键索引是非聚集索引，叶子节点存放的是主键，

InnoDB索引非主键索引存储的是主键ID，这样可以保证数据一致性和节省存储空间，可以这么理解：商城系统订单表会存储一个用户ID作为关联外键，而不推荐存储完整的用户信息，因为当我们用户表中的信息（真实名称、手机号、收货地址···）修改后，不需要再次维护订单表的用户数据，同时也节省了存储空间。（主要因为innerDB的索引和数据是在一个文件中，如果非主键索引不用主键的值，那么就意味做需要存多份数据文件）

联合索引

底层存储结构

索引最左前缀原理

先比较最左边的字段，根据最左边的字段排序，如果相等就看下一个字段。

对于这三条语句，只有第一条会走这个联合索引查询，因为联合索引是按照先后顺序排好序了，如果跳过了name直接去查，其他字段是没有排好序的。比如查询age=30，这个字段只有在name相等的时候是排好序的，其他时候是没有顺序的，这个时候如果走联合索引就要查整张表了。