[MySQL] B+树索引

B+树是一种经典的数据结构，由平衡树和二叉查找树结合产生，它是为磁盘或其它直接存取辅助设备而设计的一种平衡查找树，在B+树中

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

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

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

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

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

MyISAM中的表是以堆表的方式进行存储，堆表没有主键，因此没有聚集索引，辅助索引叶节点不是返回主键值，而是返回行标志符（ROWID），通过ROWID再去查找相应的行。

Sveil开源商城

Sveil开源商城是专业和创新的开源在线购物车的解决方案，是基于osCommerce 3 alpha 5 独立开发的项目。环境为PHP+MYSQL，使用了先进的AJAX技术和富互联网应用（RIA）的框架ExtJS，由Sveil.com提供重要的可用性改善及与网站交互界面速度更快，更高效。VERSION 1.0--修复bug1、网站在维护2、当搜索引擎被激活，与我们联系功能不起作用。3、当SEO被激

6

查看详情

很显然，对于堆表来说，通过辅助索引访问更快(IO更少)，但是如果在OLTP应用下，表中数据经常被修改，辅助索引中的ROWID可能需要经常更新，如果更新影响到物理地址的更改，这种开销比索引组织表要大得多。

因此，索引组织表还是堆表，这取决于你的应用，如果你的应用是OLAP，数据更新很少，堆表更好一些。

复合索引是指对表上的多个列做索引，下面是一个复合索引的例子：