数据库索引数据结构 B树和B+树详解

小灰灰 2022-09-05 00:09 204阅读 0赞

### 数据库索引数据结构 B树和B+树详解 ###

*  1. 常见的动态查找树
 *  2. B树和B+树概述
 *  3. B树和B+树区别
 *  4. 为什么说B+树比B树更适合数据库索引

# 1. 常见的动态查找树 #

常见的动态查找树主要有：  
二叉查找树（Binary Search Tree），  
平衡二叉查找树（Balanced Binary Search Tree），  
红黑树(Red-Black Tree )，  
B-tree/B±tree/ B\*-tree (B~Tree)。  
前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然会提高查找效率。

由于树形结构的查询效率比较高，所以大部分数据库索引都是采用树型结构进行存储的，尤其是平衡二叉树在深度不高的时候查询效率非常高，但是在大规模数据存储时，树节点存储的元素数量是有限，这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。  
这个时候B-tree/B±tree就应运而生，B-tree/B±tree就是为了解决二叉树深度过大而导致IO频繁查询效率低下的问题，B-tree/B±tree每个节点可以有两个以上的子节点，可以有效的降低树的深度，减少IO次数，从而提高查询效率。像mysql的InnoDB就是采用B+树结构，

# 2. B树和B+树概述 #

B-tree树即B树，B即Balanced，平衡的意思。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是另一种树。而事实上是，B-tree就是指的B树。

B树就是一种平衡多路查找树，其每个节点可以有两个以上的子节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTgzNjU1_size_16_color_FFFFFF_t_70]  
B+树在B树的基础上做了改进，在B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出，且每一个叶子结点都会保存一个指向后一叶子结点的指针。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTgzNjU1_size_16_color_FFFFFF_t_70 1]

# 3. B树和B+树区别 #

能直观看出来的从定义与图中也可以看出来，B树节点之间没有指针，B+树有。

1.B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。  
B树的由于每个节点都有key和data，所以查询的时候可能不需要O(logn)的复杂度，甚至最好的情况是O(1)就可以找到数据，而B+树由于只有叶子节点保存了data，所以必须经历O(logn)复杂度才能找到数据。

2.B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。  
由于B+树的叶子节点的数据都是使用链表连接起来的，而且他们在磁盘里是顺序存储的，所以当读到某个值的时候，磁盘预读原理就会提前把这些数据都读进内存，使得范围查询和排序都很快

3.B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确。  
由于B树的节点都存了key和data，而B+树只有叶子节点存data，非叶子节点都只是索引值，没有实际的数据，这就时B+树在一次IO里面，能读出的索引值更多。从而减少查询时候需要的IO次数！

# 4. 为什么说B+树比B树更适合数据库索引 #

1.B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

2.B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3.由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTgzNjU1_size_16_color_FFFFFF_t_70]: /images/20220829/09d2c9be20f04148ba0b54c2188eaf57.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTgzNjU1_size_16_color_FFFFFF_t_70 1]: /images/20220829/d1ab50a1b38047ee96da66d56bf34450.png