数据库：innodb数据组织形式

在MySQL数据库的innodb存储引擎中，数据是按照主键以B+树的形式存储的。如果在建表的时候没有指定主键，那么引擎会自动添加一列主键。

B+树

B+树是一种平衡树，即根节点到各个叶子节点的高度不超过1。在B+树中，所有记录节点都是按照键值的大小顺序存在同一层的叶子节点上，由各个叶子节点指针进行链接。B+的形式如上图所示。从上图中，如果用户从最左边的叶子节点遍历即可得到所有键值的顺序排序：4、7、10、15、25、36、50、59、61、65、75、80、85、90。

平时我们常接触的查找结构是平衡二叉树或者红黑树。为什么innodb存储引擎选择了B+树呢？首先我们知道innodb的数据存储磁盘上。由于磁盘IO相对于CPU和内存而言要慢很多，所以减少磁盘IO是提升性能的关键，另外对于机械磁盘而言顺序读取要比随机读取的性能高出1到2个数量级。我们来看上图中的例子，在查找时，可以先将根节点一次读入内存，再进行二分法查找，定位到叶子节点的位置之后，也可以一次将叶子节点加载到内存在进行查找。这样基本上只需要2次IO就能找到数据了。对于平衡二叉树或者红黑树就需要更多次的IO，并且这些IO都是离散读，性能较差。

innodb的主键又被称为聚集索引。通过聚集索引可以直接查找到整条记录（因为B+树的叶子节点就是数据节点，存储了数据）。innodb还有一种辅助索引。这是一个二级索引。它也是B+树组织的，但是叶子节点上的数据，不是数据，而是聚集索引。一个辅助索引的查找的大概过程是：在辅助索引上找到聚集索引，再通过聚集索引找到数据。可以看出相对于聚集索引，辅助索引的查找过程更长，所以一般innodb更倾向于使用聚集索引。但是也有些情况下，查找是搜索辅助索引就能完成。比如：一张表：t（a，b，c），其中a是主键，b是辅助索引，对于select b from t where b > 10或者select count(*) from t where b > 10都是不需要再查找聚集索引的。

我们上面提到了磁盘的顺序读的性能要明显高于随机读。我们再来看辅助索引的查找过程。辅助索引也是B+树组织的，叶子节点是按照辅助索引的值来排序的。这就导致了，如果我们按照辅助索引的顺序去聚集索引查找时，是随机读。innodb为了提升性能，有一种优化，对于辅助索引的范围查找，先找出这些聚集索引，再按照聚集索引进行排序，按照这个顺序去聚集索引中查找，这样可以尽量保证顺序读，并且可以充分利用缓存。