B 树和 B+ 树

B-Tree，称为 B 树，有人叫 B 减树，这是直译过来的。
B 树是一种多路平衡查找树，每一个节点最多包含 k 个孩子，k 被称为 B 树的阶。k 的大小取决于磁盘页的大小。
特征：

• 根节点至少有两个子女。
• 每个中间节点都包含 k-1 个元素和 k 个孩子。
• 每一个叶子节点都包含 k-1 个元素
• 所有叶子节点都位于同一层

• 每个节点中的元素从小到大排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分化。
  说了这么多，如果你的脑中已经有了 B 树的雏形，那么你不用看下去了，你应该去看更高级的东西。以下只是我的学习。
  我们来看一个 3 阶的 B 树：

  
  3 阶的 B 树
  

  它就满足上面所说的那些特征。
  如果现在要插入一个元素 4，那么只能这样：

  
  插入 4
  有些麻烦，因为 B 树能够为此多路平衡。
  删除的话呢，比如要删除 11：
  删除 11
  发现进行了多次变换。
  

  接下来看看 B+ 树的特征：

• 有 k 个子树的中间节点包含 k 个元素（B 树是 k-1 个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
• 所有的叶子节点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子节点本身依赖关键字的大小自小而大顺序链接。
• 所有的中间节点元素同时存在于直接点，在子节点元素中是最大（或最小）元素。
  B+ 树
  明白一个概念卫星数据，指的是索引元素指向的数据记录，比如数据库中的某一行。在 B 树中，中间节点还是叶子节点都带有卫星数据。
  B+ 树
  在数据库的聚集索引中，叶子节点直接包含卫星数据。在非聚集索引中，叶子节点带有指向卫星数据的指针
  MySQL 使用 B+ 树作为引擎的数据结构。B+ 树相比 B 树优点：

1. IO 次数少 2. 查询性能稳定； 3. 范围查询简便。

B 树可以在非叶子节点命中，而 B+ 树只有达到叶子节点才命中。
所有的关键字都出现在叶子节点链表中，且都是有序的

数据库相关

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址

图片来源于网络

InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

图片来源于网络
InnoDB的所有辅助索引都引用主键作为data域。