1.前言为了弄清楚这个问题，阿粉先带大家了解一下什么是索引。记得刚开始学数据库的时候，老师喜欢用书的目录来类比数据库的索引，告诉我们索引可以像目录一样，让我们??可以找到想要找的数据快点。如果是第一次接触索引，这个比喻可以给我们一个直观的印象。但是当我们深入索引的时候，不能继续抱着索引就是目录的想法，我们要跳出来思考索引的本质。2.索引的本质在没有索引的情况下，我们只能从头到尾逐行查找数据。我们每搜索一行数据，就意味着我们要到磁盘上相应的位置去读取一条数据。如果查询一条数据分为两步：查询磁盘和比较查询条件，那么查询磁盘的时间会比比较查询条件的时间长很多，也就是说在一次查询中，磁盘IO占用了很多时间。此外，查询的效率取决于磁盘ios的数量。如果我们能在一次查询中尽可能地减少磁盘ios的数量，那么我们就可以加快查询速度。知道减少磁盘io可以加快查询速度后，我们就需要关注如何减少磁盘io了。如果按照原表逐行查询，n条数据需要查询n次，时间复杂度为O(N)。为了减少磁盘io的次数，我们必须使用查询时间复杂度较低的数据结构来保存数据。这种查询时间复杂度低的数据结构称为索引。所以通俗地说，索引其实就是某种数据结构，有多种数据结构可以作为索引。3、索引的选择由于索引是一种便于查询的数据结构，如果对数据结构有一定的了解，大概率会首选树结构。毕竟树结构一般查询时间复杂度为O(logN)，插入和删除数据的性能比较一般。（可能你会说数组和哈希表的查询速度也很高，这个后面会分析）虽然我们已经知道Mysql中最常用的引擎，比如InnoDB和MyISAM，最终还是选择了B+树作为索引，不过这里我还是打算从最常见的二叉树入手，推导为什么最后选择B+树作为索引，比较几种树结构作为索引的优缺点。最常见的二叉树的问题是不能保证O(logN)的查询时间复杂度。我们看下图：由于插入的元素逐渐增加，所以元素总是向右插入，一颗好的二叉树最终变成了“链表”。在这种极端情况下，二叉树的查询时间复杂度不再是O(logN)，而是退化为O(N)，显然不满足索引的要求。Balancedbinarytree(red-blacktree)平衡二叉树和红黑树一样，不管元素怎么插入，他都可以通过一些轮换的方法调整树的高度，这样整棵树的查询效率是保持在O(logN)，如下图所示：这样他就满足了成为指标的前提条件，但最终没有被选为指标，说明还是有不足。如果仔细观察，可以发现平衡二叉树的每个节点只有两个子节点。如果一个表的数据量特别大，那么整个树的高度也会相应增加。如果千万级的表用平衡二叉树做索引，树高会达到20多层。这也意味着需要20多个磁盘io做一次查询，这是一个不小的开销。那么有没有一种树结构可以在数据量很大的情况下保持较小的树高呢？B-tree和B+树的答案就是B-tree。上面我们提到平衡二叉树的瓶颈是一个节点只有两个子节点，而B树节点可以存储N个子节点，完美解决了树高的问题。我们可以把B树称为balancedmulti-forktree，B-treeasindex如下图所示：图片来自网络，但是B树的结构还是有可以优化的地方树作为索引。我们先来看最终的B+树，然后在B-tree的基础上仔细分析B+树。B+树有哪些改进，为什么终于可以做索引的工作了：图片来源网络从图中可以看出，B+树也是一棵多差平衡树，解决了树高的问题B树也是如此。改进点1：但是仔细看可以发现，B-tree的节点既存储了索引，也存储了表对应的数据；而B+树的非叶子节点不存储数据，只存储索引，所有数据都存储在叶子节点上。.为什么会有这样的改善？让我们算算一次。假设树高为2，主键ID为bigint类型，长度为8字节，节点指针为6字节，一行数据记录大小为1k，一次io操作可以获得一页16k数据.以B+树索引为例，根节点可以存储：16k/(6+8)=1170个索引指针；第一层总共可以指向1170*1170=1368900个索引指针；在最底层的叶子节点，一个节点可以存储16k/1k=16条记录，总共可以存储1170*1170*16=21902400条记录。在B-tree的情况下，由于非叶子节点使用大量的空间来存储数据，所以存储的索引指针必须在最后，如果整棵树要存储和B+树一样多的数据，则高度必须增加树，增加了磁盘io，所以B+树作为索引的性能要高于B树。改进2：叶子节点之间使用指针连接，提高区间访问效率。如果我们要进行范围查询，我们可以很方便地遍历B+树叶子节点之间的指针，减少不必要的磁盘io。总结看到这里，相信大家对Mysql常用引擎为什么默认使用B+树作为索引有了初步的了解。我们只需要记住一件事：索引的存在是为了减少磁盘io并提高查询性能。最后，我想回答一下为什么哈希表和数组不常用作索引。哈希表中单个值的查询效率虽然很高，但是不能支持范围查询。哪个公司的业务没有范围查询？数组虽然查询效率高，但是增删改查效率低，因为在增删改查记录的时候要维护索引，会导致在记录量大的情况下增删改查效率低数据的。
