Btree/B+tree原理及区别（详解）

1，B-tree

• 什么是B-tree

B-tree是一种多路自平衡搜索树，它类似普通的二叉树，但是Btree允许每个节点有更多的子节点。Btree示意图如下：

• 由上图可知 B-tree 的一些特点:

1,所有键值分布在整个树中
2,任何关键字出现且只出现在一个节点中
3,搜索有可能在非叶子节点结束
4,在关键字全集内做一次查找，性能逼近二分查找算法

1、一棵m阶的B-Tree有如下特性

1. 每个节点最多有m个孩子。
2. 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子(Ceil返回大于或者等于指定表达式的最小整数)。
3. 若根节点不是叶子节点，则至少有2个孩子
4. 所有叶子节点都在同一层，且不包含其它关键字信息
5. 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）
6. 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n)为关键字，且关键字升序排序。
8. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)

2、以一个3阶的B-Tree举例

1. 每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。
2. 两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。
3. 以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

模拟查找关键字29的过程

'''模拟查找关键字29的过程：'''
# 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
# 比较关键字29在区间（17,35），找到磁盘块1的指针P2。
# 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
# 比较关键字29在区间（26,30），找到磁盘块3的指针P2。
# 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
# 在磁盘块8中的关键字列表中找到关键字29。

2，B+tree

B+树是B树的变体，也是一种多路平衡查找树，B+树的示意图为：

• 由图可看出B+tree的特点 同时也是 B-tree 和 B+tree的区别

1，所有关键字存储在叶子节点，非叶子节点不存储真正的data
2，为所有叶子节点增加了一个链指针
3，层级更低，IO 次数更少
4，每次都需要查询到叶子节点，查询性能稳定
5，叶子节点形成有序链表，范围查询方便

B+tree特点

1. B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。
2. 从上一节中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。
3. 而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小
4. 当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。
5. 在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息， 这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

B-tree/B+tree区别

1）非叶子节点只存储键值信息。
2）数据记录都存放在叶子节点中
3）B+tree的所有关键字存储在叶子节点，非叶子节点不存储真正的data。
4）B+tree为所有叶子节点增加了一个链指针。
5）B+tree支持叶子节点的延展性（横向性）

B+tree(以每个节点可存4个建值及指针信息为例)

1. B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息
2. 在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。
3. 因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

B+Tree优点

1. InnoDB存储引擎中页的大小为16KB(linux中)，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节(win中)
2. 也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（这里的K取值为〖10〗^3）。
3. 也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。
   说明：
   实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。
   mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

B-tree与哈希索引的区别

1）B+tree的索引：
是按照顺序存储的，所以，如果按照B+tree索引，可以直接返回，带顺序的数据，但这个数据只是该索引列含有的信息。因此是顺序I/O
适用于： 精确匹配 、范围匹配 、最左匹配
2）Hash索引：
索引列值的哈希值+数据行指针：因此找到后还需要根据指针去找数据，造成随机I/O
适合： 精确匹配
不适合： 模糊匹配 、范围匹配 、不能排序