1. B+树原理
Q: 为什么使用索引会加快查询速度？
没有索引的情况
如果没有使用索引，是按照表的顺序遍历的，不论查询几条数据，MySQL需要将表的数据从头到尾遍历一遍。
有索引的情况
在我们添加完索引之后，MySQL一般通过B+树算法生成一个索引文件，在查询数据库时，找到索引文件进行遍历，在比较小的索引数据里查找，然后映射到对应的数据，能大幅提升查找的效率。
Q: 为什么要用B+树？
可以从几个维度去看这个问题：查询是否够快，效率是否稳定，存储数据多少，以及查找磁盘次数。
为什么不用二叉树？
普通二叉树存在退化的情况，如果它退化成链表，相当于全表扫描。平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。
为什么不用平衡二叉树？
读取数据的时候，是从磁盘读到内存。如果树这种数据结构作为索引，那每查找一次数据就需要从磁盘中读取一个节点，也就是一个磁盘块，但是平衡二叉树每个节点只存储一个键值和数据，如果是B+树，可以存储更多的节点数据，树的高度也会降低，因此读取磁盘的次数就降下来了，查询效率就快。
为什么不用B树？
B+树和B树的查询过程差不多，但是B+树和B树有个根本的差异在于，B+树的中间节点并不直接存储数据：
查询效率更稳定：因为B+树每次只有访问到叶子节点才能找到对应的数据，而B树中，非叶子节点也会存储数据，这样就会造成查询效率不稳定的情况
查询效率更高：通常B+树比B树更矮胖（阶数更大，深度更低），因为B+树在非叶子节点不存储数据，所以就会有更多的目录项，分叉就会多一些，I/O也会更少
范围查询效率高：所有关键字都出现在B+树的叶子节点中，叶子节点之间会有指针，数据是递增的（是有顺序的），这使得范围查找可以通过指针链接查找；B树中则需要通过中序遍历才能完成查询范围的查找，效率低很多
为什么不使用Hash？
范围查询性能差：Hash索引仅能满足=、!=、IN的查询；如果进行范围查询，时间复杂度会退化为O(n)；而树型的"有序"特征，依然能够保持O(log₂N)的高效率
不支持排序：Hash索引数据存储是没有顺序的，在ORDER BY的情况下，使用Hash索引还需要对数据重新排序
不支持联合索引的部分查询：对于联合索引，Hash是将联合索引键合并到一起去计算，无法对单独的一个键或者几个索引键进行查询
Hash冲突影响性能：索引列的重复值如果很多，效率会降低，这是因为遇到Hash冲突时，需要遍历桶中的行指针进行比较，找到查询的关键字，非常耗时
Q: B+树的结构是怎样的？
节点结构
- 根节点：包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块
- 非叶子节点：只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中
- 叶子节点：真实的数据存在于叶子节点，即3、4、5……、65
关键特征
- 叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表，可以进行范围查询