MySQL索引：B+树索引

database

B+树索引是传统意义上的索引，这是目前关系型数据库系统中查找最为常用和最为有效的索引。B+树索引的构造类似于二叉树，根据键值快速找到数据

B+树是由B树演化而来的，在了解B+树之前，我们需要对B树有一点认知。

B树全称Balance-tree(平衡多路查找树)定义如下：

所有的非叶子结点中包含以下数据：（n，A0，K1，A1，K2，…，Kn，An）
其中：
Ki（i=1,2,…,n）为关键码，且Ki<Ki+1（注：ki是真实数据，存放在线性表当中，且从左至右升序排列）
Ai 为指向儿子的指针(i=0,1,…,n)，且指针Ai-1 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn。（注：每个ki数据两旁各安放了一个指针，即Ai-1和Ai，左边的子树数据统统小于ki，右边子树的数据统统大于ki）（注：总体来看指针数量比数据数量多1）
n 为关键码的个数（[m/2]-1≤n≤m-1）。

所有的叶子结点都出现在同一层次上，即所有叶节点具有相同的深度，等于树高度。并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

B+树是为磁盘或者其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。

B树每个节点都存储数据，所有节点组成这棵树。B+树只有叶子节点存储数据（B+数中有两个头指针：一个指向根节点，另一个指向关键字最小的叶节点），叶子节点包含了这棵树的所有数据，所有的叶子结点使用链表相连，便于区间查找和遍历，所有非叶节点起到索引作用。

B树中叶节点包含的关键字和其他节点包含的关键字是不重复的，B+树的索引项只包含对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

B树中每个节点（非根节点）关键字个数的范围为m/2(向上取整)-1,m-1，并且具有n个关键字的节点包含（n+1）棵子树。B+树中每个节点（非根节点）关键字个数的范围为m/2(向上取整),m，具有n个关键字的节点包含（n）棵子树。

B+树中查找，无论查找是否成功，每次都是一条从根节点到叶节点的路径。

一颗高度为2的B+树

聚集索引是按照每张表的主键构造的一颗B+树，同时叶子节点中存放的即为整张表的行为记录数据，也将聚集缩影的叶子节点成为数据页。

由于实际的数据页只能按照一颗B+数进行排序，因此每张表只能拥有一个聚集索引。此外，由于定义了数据的逻辑顺序，聚集索引能特别快的访问针对范围值的查询。

在辅助索引中，叶子节点不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签(bookMark)。概述前用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据

辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表尚客优有多个辅助索引