MySQL_B+Tree索引

索引是提高查询效率的，在MySQL中以B+树索引为主（绝大部分MySQL数据库引擎都是用的Innodb，而Innodb默认使用B+树）。
B+树索引又分为聚簇索引和非聚簇索引，本文着重介绍聚簇索引。

聚簇索引

聚簇索引并不是单独的索引类型（索引类型包含：主键索引、唯一索引、单列索引、聚合索引等），而是一种数据存储方式。其非叶子节点仅包含索引列，数据行存储在叶子节点上。
Innodb只保证相同页上的数据是连续的，但不同的页可能相距甚远。

结构

1. 类似平衡二叉查找树：节点有序(左节点<根节点<右节点)，树是平衡的不会单边增长。
2. 节点上存有多个索引值，控制树的深度，稳定查询效率。
3. 节点大小是一个页4KB。

B-Tree和B+Tree的对比

B-Tree

B+Tree

聚簇索引的优点

1. 叶子节点包含数据行，因此聚簇索引比非聚簇索引更快。
2. 叶子节点中的数据是连续的，实现范围查找效率更高（叶子节点之间有顺序指针）。
   

聚簇索引的缺点

1. 更新聚簇索引代价很高，以为需要移动数据行到新的位置。
2. 可能导致页分裂，从而某时刻导致大量的I/O操作。

---

参考资料：

1. 8.3.1 How MySQL Uses Indexes
2. 8.3.9 Comparison of B-Tree and Hash Indexes
3. 8.3.6 Multiple-Column Indexes
4. covering index
5. Mysql索引简明教程
6. 聚簇索引及 InnoDB 与 MyISAM 数据分布对比
7. 不准犹豫！再有人问你为什么MySQL用B+树做索引，就把这篇文章发给她