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 树优点：
- IO 次数少 2. 查询性能稳定； 3. 范围查询简便。
B 树可以在非叶子节点命中，而 B+ 树只有达到叶子节点才命中。
所有的关键字都出现在叶子节点链表中，且都是有序的
数据库相关
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址
图片来源于网络
InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
图片来源于网络
InnoDB的所有辅助索引都引用主键作为data域。
网友评论