【索引专题】索引底层实现连环炮
本问题对应的项目链接：高频题回答模版训练
说明：索引底层实现是问的最多的了，这部分要掌握的好，需要对常见数据结构要了解，这样你才能信手拈来，下面大家逐一回答。
1、介绍一下 mysql 索引？
2、为什么索引要采用 B+ 树？用其他数据结构不可以吗？比如哈希表，B树，红黑树（指导：主要从**支持范围查找+减少磁盘操作+树的查找速度快** 这几个方面说）。
3、介绍一下B+树是怎么分裂的？
4、刚才说到了 B 树，B 树和 B+ 树的主要区别是什么？可以讲一讲 B 树的应用场景吗？
shuaidi
共以下 4 个回答
1、介绍一下mysql索引
索引充当如同书页目录一样的功能方便我们查找库中的数据，在InnoDB引擎中Mysql的索引是通过B+树的结构在存储，B+树的叶子结点通过有序的链表相连，在范围查询时可以获得更快的速度，同时只有叶子节点存放Value，其他节点存放的是主键key，因此可以一次加载更多的节点在内存中，减少磁盘加载到内存的次数。Mysql的索引分为主键索引和普通索引，主键索引可以直接通过查询得到数据，而使用普通索引则需要通过一次回表到主键索引上才能得到数据，因此在使用索引时尽量使用主键索引。如果必须使用普通索引的话，可以通过覆盖索引、最左前缀原则、索引下堆等方式减少回表次数，以减少资源消耗。在使用索引查找的时候要注意sql语句的书写，书写操作不当可能不会引发索引查找，比如在sql语句中进行函数操作等。同时系统也会自主判断走索引是否会更快从而决定是否走索引，主要通过索引的区分度来判断，一个索引上不同的值越多，意味着出现相同数值的索引越少，索引区分度也就越大，区分度越大走索引就越有优势，但是系统在判断索引区分度的时候是通过采样的方式遍历部分数据，因此可能会出现判断不准确的情况从而走全表扫描，此时可以在sql语句里加上force关键字让系统强制走索引。
2、为什么索引要采用 B+ 树？用其他数据结构不可以吗？比如哈希表，B树，红黑树（指导：主要从**支持范围查找+减少磁盘操作+树的查找速度快** 这几个方面说）
哈希表利用键值对储存数据，在查找单个数据的时候可以做到O(1)的时间复杂度，但是在批量查找数据的时候必须走全表扫描，而B+树的叶子结点均通过链表相连，可以按顺序一次性读取范围查找的数据。红黑树每个节点只有一个数据，相比于B树来说树的高度会更加高，而树类结构的时间复杂度又和树的高度有关，相比于B树来说，B+树只有叶子节点储存Value值，因此可以一次性加载更多的数据到内存中，从而减少IO的读写次数。
3、介绍一下B+树是怎么分裂的？
B+树分裂时是从叶子节点开始的，接着是其父节点，一层一层的往上分裂，直到每个节点的子节点数不超过B+树的阶数为止。其中每个结点在分裂时，都是选取节点的中间大小元素，将这个元素向上移至父节点，然后检查父节点所在的节点数是否超过 B+ 树的阶数，不超过则结束，超过则继续重复这个过程。
4、刚才说到了 B 树，B 树和 B+ 树的主要区别是什么？可以讲一讲 B 树的应用场景吗？
1、介绍一下 mysql 索引？
解释一下索引，类比一个例子；
索引的优缺点
2、为什么索引要采用 B+ 树？用其他数据结构不可以吗？比如哈希表，B树，红黑树（指导：主要从支持范围查找+减少磁盘操作+树的查找速度快 这几个方面说）。
分配页空间是固定的，一般为16kb，非叶子节点只用来存放索引，叶子节点存档数据，可以较少io磁盘读写的次数，提高查询的效率；
范围查询，指针；
全表查询效率固定；
哈希表，适用于“等值查询”，select查询时通常都不止一条数据，需要哈希多次，效率低；
B树：非叶子节点存放了数据+索引；全表扫面、类似于二分查找、不固定；叶子节点相互独立；查询多条数据时需跨层读取，效率低，IO磁盘读取成本大、
红黑树：
***3、介绍一下B+树是怎么分裂的？
B树的分类是从叶子节点开始的，若叶子节点包含的元素个数大于等于m的阶数后，开始一层一层的向上裂变，裂变的元素是按m/2来计算的，并把这个位置的元素插入父节点中，左半部门插入父节点的左边，右半部分插入父节点的右边；
当父节点满了之后，重复裂变即可；
4、刚才说到了 B 树，B 树和 B+ 树的主要区别是什么？可以讲一讲 B 树的应用场景吗？
范围查询、全表扫描、非叶子节点存放的数据
索引就是为了加快数据查询。相当于书的目录。当然索引不一定会提高数据库的查询性能，还有可能会降低数据库的查询性能。因为索引也需要维护成本，并且有时候错误的sql语句会导致索引失效，另外有时候mysql也会选择错误的索引。只有在建立合适的索引并且编写正确的sql语句确保MySQL可以选择正确的索引的情况下，才会优化数据库的查询性能。
因为B+树是专门被设计用在访问磁盘或者其它外接存储设备的数据结构。首先，它是多叉树，树的子节点越多，存储越多数据时的树的高度就越小。树高为4时，就可以存储10亿左右的数据。这样一来最多只需要4次IO操作，就可以读取到任意一行数据。减少了磁盘操作。并且树的非叶子节点存储顺序所有子节点上面最大的键值，这样就可以通过二分查找快速定位要去哪一个子节点上面查询数据。查找速度快。另外就是树的叶子节点才存储行数据。同一个页上的不同行数据之间通过双向链表串起来，不同页也是通过双向链表串起来，所以支持范围查询。
哈希表不支持范围查询。B树也不支持范围查询。红黑树和二叉平衡树在数据量大的时候树的高度可能会很高。
比如页1上面数据满了，现在插入一条数据，为了维护B+树的有序性，这条数据需要在页1上面，于是把需要将页1上面数据一部分转入另外的页，如果另外页有空闲位置，就放进去，做旋转操作，如果也满了，就需要做页拆分。无论是旋转还是拆分，还需要依次维护上层父节点的数组有序性。
B树的数据可以在非叶子节点上面，B+的数据在叶子节点上面。
B树用于文件系统，这样一来可以减少磁盘的IO操作，因为B树上的叶子节点可以存储数据，当访问一个目录时，只需要找到对应的叶子节点就可以查询到该目录下的文件信息和目录信息，如果还需要访问里面的目录信息，再执行一次IO操作就可以访问。
1、介绍一下 mysql 索引？
MySQL 的索引就和书的目录一样，通过索引可以快速查找表中的数据。MySQL 中有很多引擎，不同引擎的索引实现不同，现在主要讲讲 InnoDB 相关的。
InnoDB 中，索引的底层实现是 B+ 树。B+ 树的节点都是有序的，查找速度很快。而且 B+ 树的非叶子节点只存键值，叶子节点才会存储具体的数据，这样能减小整个树的大小，方便内存可以一次加载更多节点。除此之外，B+ 树的叶子节点间是用双向链表串联起来的，便于范围查找。范围查找也是 MySQL 中经常出现的操作。
另外平常在写 SQL 的时候还需要注意，有些操作可能会导致索引失效，比如在 SQL 中使用函数，LIKE 查询并且把通配符 % 放在第一位，都是会导致索引失效的。
虽然大多数时候索引都能加快查询速度，但也不是绝对的，有时候不走索引可能比走索引还快，所以有时即使正确的加了索引，系统也有可能不走索引。关于走不走索引，MySQL 是利用索引的区分度来判断的。一个索引的不同值越多，区分度就越大，走索引就越有优势。
所以有时候，系统如果觉得走了索引需要扫描更多行数的话，它就不走索引了，而是扫描全表。
但是系统也有预测错误的时候，因为 MySQL 是通过遍历一部分数据，也就是用采样的方式，来预测索引的区分度的。有时候采样会出现大的误差，就会出现该走索引的时候没有走。这时候可以通过 analyze table 语句重新统计一下索引信息来解决。有些极端情况 MySQL 还是会走错索引，这个时候可以加上 force 关键字来强制走某个索引。
然后大概能说这么多。
2、为什么索引要采用 B+ 树？用其他数据结构不可以吗？比如哈希表，B树，红黑树（指导：主要从支持范围查找+减少磁盘操作+树的查找速度快** 这几个方面说）。**
先说下 B+ 树的优点，首先它是一个 N 叉平衡树，也就是一个节点含有 N 个子节点，这样做可以降低树的高度，同时也可以让一个查询尽可能少的读磁盘。除此之外，B+ 树的非叶子节点只存 key 不存 value，这样在相同的内存下，可以增多每次加载进内存的节点数量。还有 B+ 树的叶子节点之间使用双向链表相连，可以很好的支持常见的范围查询操作。
那么哈希表主要是用在 “等值查找” 的场景，能根据一个 key 在 O(1) 时间内返回它的 value，但在 “范围查找” 的场景下只能进行全表扫描，效率很慢。
有序数组在 “等值查找” 和 “范围查找” 的查询场景中性能很优秀，可以按照某个字段值递增，来构建一个有序数组，那么查询时用二分法就可以快速得到。不过缺点是有序数组在更新数据的时候效率很低，插入或删除某个数据时，都必须依次移动后面的所有记录，
二叉搜索树的话，它的查找更新性能都不错，都是 O(logN)，但是有一个问题，就是节点非常多的情况下，树的高度相较于 B+ 树也会非常高。一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。对于 B+ 树，当底层的 N 叉树 n = 1200 时，10 亿级的数据查询某个整数字段最多也只需查询 3 个数据块，相应的磁盘 IO 也就少的多了。
3、介绍一下B+树是怎么分裂的？
B+ 树分裂时是从叶子节点开始的，接着是其父节点，一层一层的往上分裂，直到每个节点的子节点数不超过 B+ 树的阶数为止。
其中每个结点在分裂时，都是选取节点的中间大小元素，将这个元素向上移至父节点，然后检查父节点所在的节点数是否超过 B+ 树的阶数，不超过则结束，超过则继续重复这个过程。
4、刚才说到了 B 树，B 树和 B+ 树的主要区别是什么？可以讲一讲 B 树的应用场景吗？
一个是 B+ 树的所有数据只存在于叶子节点中，而 B 树中的每个节点都存有数据。另一个是 B+ 树的叶子节点是通过双向链表相连，便于范围查询，B 树没有。
B 树的主要优点是优化了磁盘访问和减少磁盘 I/O 次数，大多数时候用在文件系统中，比如在 Windows NTFS 文件系统中，每个目录都对应着一个 B 树节点，可以快速地对文件进行查找和访问，提高文件系统性能。