MySQL的B+树索引

本文讨论MySQL支持的索引类型及其优缺点。要注意的是：在MySQL中，索引是在存储引擎层而不是服务器 层实现，所以不同存储引擎的索引的工作方式并不一样，也不是所有的存储引擎都支持所有类型的索引。

B+树是一种经典的数据结构，由平衡树和二叉查找树结合产生，它是为磁盘或其它直接存取辅助设备而设 计的一种平衡查找树，在B+树中，所有的记录节点都是按键值大小顺序存放在同一层的叶节点中，叶节点间 用指针相连，构成双向循环链表，非叶节点（根节点、枝节点）只存放键值，不存放实际数据。下面看一个2 层B+树的例子：

保持树平衡主要是为了提高查询性能，但为了维护树的平衡，成本也是巨大的，当有数据插入或删除时， 需采用拆分节点、左旋、右旋等方法。B+树因为其高扇出性，所以具有高平衡性，通常其高度都在2~3层，查 询时可以有效减少IO次数。B+树索引可以分为聚集索引(clustered index)和非聚集索引（即辅助索引， secondary index）。

聚集索引

InnoDB表时索引组织表，即表中数据按主键B+树存放，叶子节 点直接存放数据，每张表只能有一个聚集索引。

辅助索引

辅助索引（也称非聚集索引）是指 叶节点不包含行的全部数据，叶节点除了包含键值之外，还包含一个书签连接，通过该书签再去找相应的行 数据。下图显示了InnoDB存储引擎辅助索引和聚集索引的关系：

从上图中可以看出，辅助索引 叶节点存放的是主键值，获得主键值后，再从聚集索引中查找整行数据。举个例子，如果在一颗高度为3的辅 助索引中查找数据，首先从辅助索引中获得主键值（3次IO），接着从高度为3的聚集索引中查找以获得整行 数据（3次IO），总共需6次IO。一个表上可以存在多个辅助索引。