相关的数据结构
在InnoDB存储引擎中，建立索引所使用的数据结构是B+树。这里我们看看和B+树相关的数据结构。
二叉树
我们把最多能有2个子节点的树称为二叉树。
二叉树
二叉树的分类
- 满二叉树：从高到低，除了叶节点外，所以节点左右节点都存在。
- 完全二叉树：从root到k-1 层（树只有k层）的节点树都达到最大，第k层的所有节点都 连续集中在最左边。
- 平衡二叉树（AVL树）：左右两个子树的高度差的绝对值不超过1，并且左右两个子树也都是平衡树。
- 二叉搜索树：空树或者二叉树的所有节点比他的左子节点大，比他的右子节点小。
- 红黑树：不仅是具有二叉搜索树的属性，还具有平衡树的属性，有序且子树差不超过1，颜色规则：根节点和特殊节点（即叶节点下面两个虚无的节点和未填写的节点）是黑的，红节点的左右子节点是黑的，最重要的是对于每个节点，从该节点到子孙叶节点的所有路径包含相同数目的黑节点。
B-树
B-树是一种多路平衡查找树。如果它的每一个节点最多包含k个子节点，k被称为树的阶。
其定义很复杂，阶为M的B-树的定义如下：
- 每个节点最多有M个子节点；
- 除了root节点之外，每个非叶子节点至少包含（M/2）个子节点；
- 如果root节点不为空，则root节点至少要有两个孩子节点；
- 一个非叶子节点如果含有k个子节点，则它需包含k-1个key；
- 所有叶子节点都在同一层；
- B-Tree中的非叶子节点也包含了数据部分。
下面给出两个B-Tree的图，我们可以直观地感受一下：
B-Tree示例1
B+树
在B树的基础上， B+树做了如下改进
- 数据只存储在叶子节点上，非叶子节点只保存索引信息；
- 叶子节点本身按照数据的升序排序并通过指针进行链接；
高度为2的B+树
根据上面B+树的图，我们可以得到以下信息：
- 该B+树的高度为2；
- 每个叶子节点中有4条记录；
- 叶子节点由大到小串联起来；
- 扇出(fanout)数为5。
扇出 是每个索引节点(Non-LeafPage)指向每个叶子节点(LeafPage)的指针
B+树需要保持其自身的平衡，所以在对其进行插入或删除的时候，可能会进行旋转或拆分页以达到平衡。
聚集索引和二级索引
在InnoDB存储引擎中，表都是根据主键的顺序进行存放的，我们将这种存储方式称之为索引组织表。
InnoDB表的主键
InnoDB存储引擎的表中，都会存在一个主键，如果在建表时没有指定主键，InnoDB会隐式地创建一个主键。InnoDB主键创建的规则如下：
- 如果建表时定义了主键，则用指定的主键；
- 如果表没有定义主键，且存在非空unique列，则选择第一个非空unique列为主键；
- 如果表即没有指定主键又不存在非空unique列，则InnoDB会创建一个6字节隐藏的row-id作为主键。
数据准备
表
t(id PK, name KEY, sex, flag);
数据
1, shenjian, m, A
3, zhangsan, m, A
5, lisi, m, A
9, wangwu, f, B
聚集索引
聚集索引即为主键索引，它是按照每张表的主键构造的一颗B+树，该B+树的叶子节点中存放的是整行记录的数据。由于聚集索引是按照主键的顺序进行排列，所以一张表中只能有一个聚集索引。
针对上面的表t，其聚集索引所对应的B+树如下所示：
聚集索引
辅助索引
辅助索引（secondary index）底层存储使用的数据结构也是B+树，它和聚集索引的区别是：辅助索引的叶子节点不包含整行记录，而是创建辅助索引的列值和一个书签(书签可以理解成指针，) 。辅助索引的存在并不会影响聚集索引，所以一张表上可以有多个非聚集的辅助索引（secondary index）。
如果在表t中的name列创建一个索引，其secondary index所对应的B+树如下图所示：
辅助索引
辅助索引的查询
当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引并通过叶子节点获取指向主键索引的主键，然后再通过主键索引去找寻完整的行记录。对于上面的例子，如果我们select * from t where name=‘lisi’;
辅助索引中的查找
我们可以看到本次查找一共进行了6次IO操作（辅助索引中3次+聚集索引中3次）。从这里我们可以知道使用辅助索引进行查找为啥要比聚集索引慢的原因了。
这里有一点需要注意，B+树索引并不能找到一个给定键值的具体行，它能找到的是被查找行所在的页，接着数据库会把页读入到内存，再在内存中进行数据所在行的查找。一般而言，页的大小为16K，一个页中能存放的记录数=16K/行的大小，对于上面的图示的聚集索引和辅助索引我们假设一个页中只存一条记录。
参考
1分钟了解MyISAM与InnoDB的索引差异.58沈剑
网友评论