为什么MySQL索引结构是B+tree ?

● 必答内容：
其实这个问题，我们可以做一个假设啊。
● 假设索引结构是二叉搜索树、平衡二叉树 或 红黑树等，其实本质都是二叉树，一个节点下最多只能有两个子节点，如果这张表要存储的数据量比较大，二叉树的层级将会非常深，检索效率会很低。
● 而如果索引结构是Btree，在B树中，非叶子节点和叶子节点既要要存储key和指针，还要存放数据，而InnoDB的物理存储结构中，一页（Page）的大小是固定的，就是16KB。 那这一页中能够存储的key的数量并不多，就会造成大数据量情况下，树的层级较深，检索速度慢。 还有一个问题，就是由于 非叶子节点和叶子节点既要要存储key，还要存放数据，查找效率并不稳定。 （有些数据，只需要一次查找，有些数据，可能需要五六次，有些...）
所以，在MySQL数据库中才使用了B+tree作为索引的数据结构。 主要有以下优势：
● 在B+tree中，非叶子节点并不存放数据，只存放key和指针，所以一页（Page）中能够容纳的key将更多，相同数据量的情况下，树的层级要浅的多，检索效率高。
● 所有的数据都存储在B+tree的叶子节点中，也就意味着无论什么数据，都需要找到叶子节点才能查询到对应的数据，检索效率更加稳定。
● 第三是B+树数据都存储在B+tree的叶子节点，并形成了一个双向链表，便于区间范围查询。
● 可能继续发问的问题：
那MySQL的B+tree的索引结构，树的高度一般是多高呢？
嗯，这个高度其实是可以计算出来的，一般高度在2-3层，如果高度为3，基本上就可以容纳一两千万的数据了。如何计算呢？
● 我们的索引是在页（Page）中存储的，而一个页的大小模式为（16KB）。
● 对于非叶子节点来说，页中存储的除了具体的key之外，还有一个就是指针 。(假设主键为bigint占8个字节，指针占6个字节)
● 那么我们就可以大概计算出一页中可以存储的key数量为：16 1024 / 14 = 1170 。也就意味着一个页（Page）中约可以存1170个key
● 假设一行数据的大小为1KB，一页可以存16条数据。那两层的B+tree可以容纳：117016=18720条数据。
● 那三层的B+tree可以容纳：1170 1170 16 = 21902400 条数据。
● 帮助理解的图示：