mysql索引的数据结构，为什么用b+树

B+ 树是对 B 树的一个小升级。大部分数据库的索引都是基于 B+ 树存储的。MySQL 的 MyISAM 和 InnoDB 引擎的索引都是基于 B+ 树存储。

B+ 树最大的几个特点：

1. 非叶子节点只保留 KEY，放弃 DATA；

2. KEY 和 DATA一起，在叶子节点，并且保存为一个有序链表（正序，反序，或者双向）；

3. B+ 树的查找与 B 树不同，当某个结点的 KEY 与所查的 KEY 相等时，并不停止查找，而是沿着这个 KEY 左边的指针向下，一直查到该关键字所在的叶子结点为止。

事实上，在MySQL数据库中，诸多存储引擎使用的是B+树，即便其名字看上去是BTREE。

4.1 innodb的索引机制

先以innodb存储引擎为例，说明innodb引擎是如何利用B+树建立索引的

首先创建一张表：zodiac，并插入一些数据

对于innodb来说，只有一个数据文件，这个数据文件本身就是用B+树形式组织，B+树每个节点的关键字就是表的主键，因此innode的数据文件本身就是主索引文件，如下图所示，主索引中的叶子页（leaf page）包含了数据记录，但非叶子节点只包含了主键，术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起，因此这种索引被称为聚簇索引，或聚集索引。

这种索引方式，可以提高数据访问的速度，因为索引和数据是保存在同一棵B树之中，从聚簇索引中获取数据通常比在非聚簇索引中要来得快。

所以可以说，innodb的数据文件是依靠主键组织起来的，这也就是为什么innodb引擎下创建的表，必须指定主键的原因，如果没有显式指定主键，innodb引擎仍然会对该表隐式地定义一个主键作为聚簇索引。

同样innodb的辅助索引，如下图所示，假设这些字符是按照生肖的顺序排列的（其实我也不知道具体怎么实现，不要在意这些细节，就是举个例子），其叶子节点中也包含了记录的主键，因此innodb引擎在查询辅助索引的时候会查询两次，首先通过辅助索引得到主键值，然后再查询主索引，略微有点啰嗦

---