参考文章

• MySQL的索引机制(B+Tree)
• 图解MySQL索引
• Mysql中的B+Tree索引

• 树和二叉树

  1 B树

  概述

  前面介绍的查找方法均适用千存储在计算机内存中较小的文件，统称为内查找法。若文件很大且存放于外存进行查找时，这些查找方法就不适用了。内查找法都以结点为单位进行查找，这
  样需要反复地进行内、外存的交换，是很费时的。
  一棵m阶的B树，或为空树，或为满足下列特性的m叉树：

• 树中每个结点至多有m棵子树，非终端结点最多有关键字m-1个；

• 若根结点不是叶子结点，则至少有两棵子树；
• 除根之外的所有非终端结点至少有 m/2 （向上取整） 棵子树；
• 所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点（失败结点并不存在，指向这些结点的指针为空。引入失败结点是为了便于分析B树的查找性能）；
• B树是所有结点的平衡因子均等于0的多路平衡查找树。

结点的结构如图所示：

B树的查找

先看一棵3阶的B树。按B树上的定义，3阶的B树上所有非终端结点至多可有两个关键字，至少有一个关键字（即子树个数为2或3, 故又称2-3 树）

B树的插入和删除

详细内容参考严蔚敏老师版本的数据结构，文档在资料附件里面。。


7.3_2_B树的插入删除.pdf

2 B+树

概述

一颗m阶的B+树需满足如下条件：
1）每个分支结点最多有m棵子树（孩子结点）。
2）非叶根结点至少有两棵子树，其他每个分支结点至少有m/2（向上取整）棵子树。
3）结点的子树个数与关键字个数相等。
4）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
5）所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。
可以简单的认为：B树（包括B-树、B+树）是多个数组之间的链表关系。


将B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：

MySQL使用B+tree

摘录一段：
InnoDB的B+tree就是以聚集索引来组织数据的存储的，在叶子节点上，保存了数据的所有信息。非叶子结点只存储了最大关键字和其对应的指针。在 InnoDB中，因为设计之初就是认为主键是非常重要的。是以主键为索引来组织数据的存储，当我们没有显式的建立主键索引的时候，搜索引擎会隐式的为我们建立一个主键索引以组织数据存储。数据库表行中数据的物理顺序与键值的逻辑（索引）顺序相同。
而非聚集索引的非叶子结点也是存储的最大关键字和子树的指针，其叶子节点上所保存的数据为聚集索引（ID索引）的关键字的值，基于辅助索引找到ID索引的值，再通过ID索引区获取最终的数据。这个做法的好处是在于产生数据迁移的时候只要ID没发生变法，那么辅助索引不需要重新生成，不这么做的话，如果存储的是磁盘地址的话，在数据迁移后所有辅助索引都需要重新生成。

7.3_3_B+树.pdf · 资料文件 · 语雀

B+tree在InnoDB引擎中的使用

表结构

CREATE TABLE user(
  id int(11) NOT NULL primary key,
  name varchar(255) DEFAULT NULL,
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
//有如下4条数据
insert into user(id,name) values(101,’seven’),(102,’james’),(103,’tom’),(104,’mic’);

B+Tree 在 InnoDB 中的体现：在创建好表结构并且指定搜索引擎为 InnoDB之后，会在数据目录生成2个文件，分别是table_name.frm(表结构文件)，table_name.idb（数据与索引保存文件）。

聚集索引

在 InnoDB中，因为设计之初就是认为主键是非常重要的。是以主键为索引来组织数据的存储，当我们没有显式的建立主键索引的时候，搜索引擎会隐式的为我们建立一个主键索引以组织数据存储。数据库表行中数据的物理顺序与键值的逻辑（索引）顺序相同，InnoDB就是以聚集索引来组织数据的存储的，在叶子节点上，保存了数据的所有信息。

非聚集索引

如果此时针对name建了索引，会产生一个辅助索引，即name字段的索引，而此刻叶子节点上所保存的数据为聚集索引（ID索引）的关键字的值，基于辅助索引找到ID索引的值，再通过ID索引区获取最终的数据。这个做法的好处是在于产生数据迁移的时候只要ID没发生变法，那么辅助索引不需要重新生成，不这么做的话，如果存储的是磁盘地址的话，在数据迁移后所有辅助索引都需要重新生成。

主键索引（聚集索引）+辅助索引（非聚集索引）的组合使用

扩展：结点为范围值

B+tree在Myisam引擎中的使用

myisam也是用b+tree作为数据结构的。
在创建好表结构并且指定搜索引擎为 Myis.am之后，会在数据目录生成3个文件，分别是table_name.frm(表结构文件),table_name.MYD(数据保存文件),table_name.MYI(索引保存文件在Myisam中，数据区中保存的是数据的引用地址，就比如说ID为101的数据信息所保存到物理磁盘地址为 0x123456，在索引中的节点数据去中所保存的就是这个磁盘地址指针。当扫描到这个指针位置，就可以通过这个磁盘指针讲数据加载出来。
在Myisam中B+Tree的实现中比如现在不用ID作为索引了，要用name，那么他的一个展现形式有事怎么样的呢？其实他与ID作为索引是一样的，也是保存他指定的磁盘位置指针，他们是平级的。