B+ 树索引并不能找到一个给定键值的具体行。 B+ 树索引能找到的只是被查找数据所在的页。 然后数据库通过把页读入到内存， 再在内存中进行查找， 最后得到要查找的数据。

平衡二叉树

平衡二叉树的定义如下：首先符合二叉查找树的定义，其次必须满足任何节点的两个字数的高度最大差为1。最好的想能需要建立一颗最优二叉树，但是最优二叉树的建立和维护需要大量的操作，因此，用户一般只需要建立一颗平衡二叉树即可。

平衡二叉树的查询速度很快，但是维护一颗平衡二叉树的代价是非常大的。通常来说，需要1次或多次左旋和右旋来得到插入或更新后树的平衡性。因此对于一颗平衡二叉树的维护是有一定开销的，不过平衡二叉树多用于内存结构对象中，因此维护的开销相对较小。

B+树

B+树的定义十分复杂，因此只简要地介绍B+树：B+树是为磁盘或其他直接存取辅助设备而设计的一种平衡查找树，在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶节点中，各叶节点指针进行连接。

1、B+树的插入操作

B+树的插入必须保证插入后叶节点中的记录依然排序，同时需要考虑插入B+树的三种情况，每种情况都可能会导致不同的插入算法，如表5-1所示。

可以看到，不管怎么变化，B+树总是会保持平衡。但是为了保持平衡，对于新插入的键值可能需要做大量的拆分页（split）操作，而B+树主要用于磁盘，因此页的拆分意味着磁盘的操作，应该在可能的情况下尽量减少页的拆分。因此，B+树提供了旋转（rotation）的功能。

旋转发生在Leaf Page已经满了、但是其左右兄弟节点没有满的情况下。这时B+树并不会急于去做拆分页的操作，而是将记录移到所在页的兄弟节点上。通常情况下，左兄弟被首先检查用来做旋转操作。

2、B+树的删除操作

B+树使用填充因子（fill factor）来控制树的删除变化，50%是填充因子可设的最小值。B+树的删除操作同样必须保证删除后叶节点中的记录依然排序，同插入一样，B+树的删除操作同样需要考虑如表5-2所示的三种情况，与插入不同的是，删除根据填充因子的变化来衡量。

B+树索引

前面讨论的都是B+树的数据结构及其一般操作，B+树索引的本质就是B+树在数据库中的实现。但是B+索引在数据库中有一个特点就是高扇出性，因此在数据库中，B+树的高度一般都在2-4层，也就是说查找某一键值的行记录时最多只需要2-4次IO。因为当前一般的机械磁盘每秒至少可以做100次IO，2-4次的IO意味着查询时间只需要0.02-0.04秒。

数据库中的B+树索引可以分为聚集索引和辅助索引（又被称为非聚集索引），但不管是聚集还是辅助的索引，其内部都是B+树的，即高度平衡的，叶子节点存放着所有的数据。聚集索引与辅助索引不同的是，叶子结点存放的是否是一整行的信息。

1、聚集索引

InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。而聚集索引就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同B+树数据结构一样，每个数据页都通过一个双向链表来进行链接。

由于实际的数据页只能按照一棵B+树进行排序，因此每张表只能拥有一个聚集索引。在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在B+树索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。

许多文档会告诉我们：聚集索引按照顺序物理地存储数据，但是试想一下，如果聚集索引必须按照特定顺序存放物理记录，则维护成本显得非常之高。所以，聚集索引的存储并不是物理上连续的，而是逻辑上连续的。这其中有两点：一是前面说过的页通过双向链表链接，页按照主键的顺序排序；另一点是每个页中的记录也是通过双向链表进行维护的，物理存储上可以同样不按照主键存储。

聚集索引的另一个好处是，它对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户所要查询的数据。

另一个是范围查询，即如果要查找主键某一范围内的数据，通过叶子节点的上层中间节点就可以得到页的范围，之后直接读取数据页即可。

2、辅助索引

对于辅助索引（secondary index，也称非聚集索引），叶子节点并不包含行记录的全部数据，叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark）。该书签用来告诉Innodb存储引擎哪里可以找到与索引相对应的行数据。由于Innodb存储引擎是索引组织表，因此Innodb存储引擎的辅助索引的书签就是相应行数据的聚集索引键。

辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表可以由多个辅助索引。当通过辅助索引寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的记录。

举例来说，如果在一棵高度为3的辅助索引树中查找数据，那需要对这棵辅助索引数查找3次找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页。因为一共需要6次逻辑IO访问以得到最终的一个数据页。

3、B+树索引的分裂

B+树索引页的分裂并不总是从页的中间记录开始，这样可能会导致页空间的浪费。

InnoDB存储引擎的Page Header中有以下几个部分用来保存插入的顺序信息：

• PAGE_LAST_INSERT
• PAGE_DIRECTION
• PAGE_N_DIRECTION

通过这些信息，InnoDB存储引擎可以决定是向左还是向右进行分裂，同时决定将分裂点记录为哪一个。若插入时随机的，则取页的中间记录作为分裂点的记录，这和之前介绍的相同。若往同一个方向进行插入的记录数量为5，并且目前已经定位到记录（InnoDB存储引擎插入时，首先需要进行定位，定位到的记录为待插入记录的前一条记录）之后还有3条记录，则分裂点的记录为定位到的记录后的第三条记录，否则分裂点记录就是待插入的记录。

4、B+树索引的管理

查看表中索引的信息可以使用SHOW INDEX语句。

接着我们来具体讲解每个列的含义：

• Table：索引所在的表名。
• Non_unique：非唯一的索引，可以看到primary key是0，因为必须是唯一的。
• Key_name：索引的名称，我们可以通过这个名称来DROP INDEX。
• Seq_in_index：索引中该列的位置，如果看联合索引idx_a_b就比较直观了。
• Column_name：索引的列
• Collation：列以什么方式存储在索引中。可以是’A’或者NULL。B+树索引总是A，即排序的。如果使用了Heap存储引擎，并且建立了Hash索引，这里就会显示NULL了。因为Hash根据Hash桶来存放索引数据，而不是对数据进行排序。
• Cardinality：非常关键的值，表示索引中唯一值的数目的估计值。Cardinality/表的行数应尽可能接近1，如果非常小，那么需要考虑是否还需要建这个索引。
• Sub_part：是否是列的部分被索引。如果看idx_b这个索引，这里显示100，表示我们只索引b列的前100个字符。如果索引整个列，则该字段为NULL。
• Packed：关键字如何被压缩。如果没有被压缩，则为NULL。
• Null：是否索引的列含有NULL值。可以看到idx_b这里为Yes。因为我们定义的b列允许NULL值。
• Index_type：索引的类型。InnoDB存储引擎只支持B+树索引，所以这里显示的都是BTREE。
• Comment：注释。

Cardinality值非常关键，优化器会根据这个值来判断是否使用这个索引。但是这个值并不是实时更新的，并非每次索引的更新都会更新该值，因为这样代价太大了。因此这个值是不太准确的，只是一个大概的值。上面显示的结果主键的Cardinality为2，但是很显然我们表中有4条记录，这个值应该是4。如果需要更新索引Cardinality的信息，可以使用ANALYZE TABLE命令。如：

analyze table t;
show index from t;

这时的Cardinality的值就对了。不过，在每个系统上可能得到的结果不一样，因为ANALYZE TABLE现在还存在一些问题，可能会影响得到最后的结果。

另一个问题是MySQL数据库对于Cardinality计数的问题，在运行一段时间后，可能会看到下面的结果：

show index from Profile;

Cardinality为NULL，在某些情况下可能会发生索引建立了、但是没有用到，或者explain两条基本一样的语句，但是最终出来的结果不一样。一个使用索引，另外一个使用全表扫描，这时最好的解决办法就是做一次ANALYZE TABLE的操作。因此我建议在一个非高峰时间，对应用程序下的几张核心表做ANALYZE TABLE操作，这能使优化器和索引更好地为你工作。