存储结构
B+树的优点为什么不选择其他的树MySQL中B+树的高度与对应的存储数据量计算 聚簇索引
什么是聚簇索引聚簇索引的优点聚簇索引的局限 存储结构
InnoDB存储引擎使用B+树的数据结构存储数据以及索引。
B+树的优点这里我就直接说了：显著减少I/O次数，其次是查询速度稳定。
为什么不选择其他的树什么是B+树不知道？点这里了解B+树。
我们看了B+树的设计结构很容易知道，它的优点。那么为什么不选择其他的树形数据结构，比如二叉查找树（B树也有人叫B-树，其实是同一种），平衡二叉树，或者是红黑树？
其实我们只需要看一下二叉查找树的高度，就可以看出原因，因为树的高度几乎可以看作是I/O的次数。当数据为顺序的时候，比如[1，2，3，4，5，6，7，8，9]的数据，树退化成了链表，树的高度为10，查询效率自然就低了。
你可能会说那二叉平衡树呢？
是的，不可否认，二叉平衡树的高度在存储相同数据时会比二叉查找树低很多，但是我们要知道维护一颗二叉平衡树的代价是很大的。节点的旋转会造成额外的开销，当数据量过大时，往树里面插入一个随机的数据代价可能大到无法接受。
那红黑树呢？HashMap中的链表在桶中数据大于8的时候就会转化为红黑树，那查询效率是不是很高。
同样是树的高度问题，HashMap中是有多个桶的，而我们只有一个“桶”。随着存储的数据的变多,红黑树上的最短路径也会变长，那么树的高度自然就不可避免的变高了。
而我们的B+树在实际应用中的高度基本不会超过四，四基本上就足够应对大部分场景了。
MySQL中B+树的高度与对应的存储数据量计算不信的话我们可以做一个简单的计算，我们知道MySQL读取磁盘数据，一次读取16k（一页的的大小），一个非叶子节点节点包括索引+指针，我们假设一个节点的大小为14（索引8 + 指针6）字节，那么一页可以存储16*1024/(14) ≈1170个节点，那么我们非叶子节点存储的是一行数据，假设一行数据为1kb, 那么一页存储16行数据，也就是16k。
所以我们B+树的高度为2时，一页的1170个叶子节点可以指向 1170 x 16 = 18720 条数据。
那么高度为3呢？我们的叶子节点个数为，第一层1170个非叶子节点，第一层的每一个节点指向下一页的非叶子节点页，那一页里面同样存在1170个非叶子节点，每个节点对应一行数据，那么第三层的存储的最大数据为 1170 x 1170 x 16 = 21902400，两千多万条数据，约20G大小。
高度为4时就是 21902400 * 1170 = 25625808000，256亿的数据。换算成GB计算的话，约为24438GB的大小。所以一般业务场景只使用到第三层，再大一点第四层也是够用了的。
聚簇索引 什么是聚簇索引 主键索引和数据存放在一起称之为聚簇索引，聚簇索引不是一种索引，而是一种存储数据的数据结构。我们由前文知道了InnoDB的存储引擎使用B+树存储数据，那么表数据怎么存放呢？
叶子节点存放行数据，非叶子节点存放主键，并且按主键顺序排列。大家可以参见上面的B+树结构，相对的非聚簇索引存储结构，比如MyISAM结构如下
以上图片来源高性能的MySQL
聚簇索引的优点 1、可以把相关数据保存在一起。因为时按主键顺序存放的，所以存放的数据是有序的。比如说：我录入学生成绩，学生的成绩就是主键，存放顺序为 0–100，那么我在查询70-80分成绩的同学时，可能只需要一次I/O就可以读取到所有的数据，因为一次会读取一页（16k）。如果是无序的，那么就可能需要多次I/O才能完成。例如一条数据在第一页，读取一次，第二条数据在第二页，读取一次，第三条数据在第10页，读取一次。。。。。。
2、数据访问相较于非聚簇索引更快。这是由于主键索引和表数据存放在一起，找到对应的主键就找到了对应的数据，不像非聚簇索引那样，找到索引之后还需要再去表中查找数据。
3、可以使用覆盖索引查询主键。二级索引中的叶子节点，存放的索引和主键。
俗话说的好，有利必有弊。那么聚簇索引的局限性有哪些呢？
1、插入、更新数据的代价可能很大。 这个不难理解，因为我们的存储顺序是有序的，当插入或者更新数据时，可能需要移动行数据，导致页分裂的问题。
2、内存足够大时，表数据可以一次全部加载到内存中，聚簇索引基本无效。 我们知道存储结构使用B+树的目的就是减少I/O，但如果不需要[/O，我一次把数据全部读取进内存，那么聚簇索引和非聚簇索引的差别就不大了。
3、导致二级索引占用的存储空间会更大。 聚簇索引的二级索引的叶子节点包含了主键列。
4、二级索引可能需要两次索引查找。 因为不是覆盖索引的话，就需要先从二级索引中找到主键，再去聚簇索引中查找所对应的数据。
5、聚簇索引可能导致全表扫描变慢。 尤其是行稀疏，或者由于页分裂导致数据存储不连续时。