B-tree 或者是B+tree 是数据库上面常用的数据结构,这里要注意一个概念“B-tree”这里面的“-“不应该读成”B减树“,同时"B"更加不应该理解为Binary,而是Balance。中文里面通常读成"B树”但是与我们所熟悉的二叉树还是有差别的。

B-tree wiki

设计缘由

B-Tree是 binary-tree的变种,B+Tree更是B-tree的变种,设计缘由是因为磁盘上的机械运动是减慢数据存取速度的主要原因,进一步说,是因为针对数据库而数据库的大小往往都是大于内存的。(除非你有钱去弄SSD硬盘,那没人理你,跳过吧)。

如何影响读取

那么是如何加速呢,书本上的解释都是比较直白,建立一个有序树状结构,通过每个结点尽可能存储下所需字符所在的磁盘块,这样就可以通过几次查询就知道自己所需数据的位置了。而每次查询都是一次机械运动,因此应该减少查询的次数,也就是树的高度(因为每次查完都到了下一层,查的层数越多越消耗事件)。减少树的高度应该让每个结点带有更多的信息,这样在一层里面就可以读尽可能多的信息去,也就减少了机械运动的次数。

进一步,B+tree是让叶子结点携带相关信息,而释放出非叶子结点的空间,让其放入更加多的磁盘块信息,使得效率进一步提高。

与红黑树的比较

书上通过公式证明了,B-tree的高度是比红黑树少一个logt 数量级的,其实也如果你看过B-tree的定义也可以知道,B-tree的叶子结点都在同一层上的,也就是绝对的平衡,红黑树和大部分的树一样只是尽可能保持平衡。

易混淆点

B -tree 的order

国外定义B-tree的时候就提到了order这个单词,应该译作什么合适?我认为是“度”。在《计算机程序设计艺术》一书中定义的「度m」表示一个结点所能拥有的最大子女数,并且非根内结点至少拥有[m/2]个子女。

在WIKI上稍作查证,首先是中文的WIKI:

[树 的wiki词条] 注意上面的链接)

节点的度:一个节点含有的子树的个数称为该节点的度;

树的度:一棵树中,最大的节点的度称为树的度;

叶节点或终端节点:度为零的节点;

非终端节点或分支节点:度不为零的节点;

国外的WIKI

[B-tree wiki](https://en.wikipedia.org/wiki/B-tree)

Bayer & McCreight (1972), Comer (1979), and others define the order of B-tree as the minimum number of keys in a non-root node. Folk & Zoellick (1992) points out that terminology is ambiguous because the maximum number of keys is not clear. An order 3 B-tree might hold a maximum of 6 keys or a maximum of 7 keys. Knuth (1998, p. 483) avoids the problem by defining the order to be maximum number of children (which is one more than the maximum number of keys).

虽然三个出处的解释不同,但是当我们说到order时候的,除了“顺序“还应该想到可能说的是节点或者树的度。

另外在数据结构中Tree的Level也有定义

Tree_data structure wiki)

Level – The level of a node is defined by 1 + the number of connections between the node and the root.(稍微解释下就是从根到当前结点,经过结点+1的数量相当于从零开始算,就是"层")

2-3 tree(2-3 B-tree) 和 2-3-4 tree( 2-3-4 B-tree)

wiki上对于2-3树的解释

In computer science, a 2–3 tree is a tree data structure, where every node with children (internal node) has either two children (2-node) and one data element or three children (3-nodes) and two data elements. Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements.2−3 trees were invented by John Hopcroft in 1970.

wiki上对于2-3-4树的解释

In computer science, a 2–3–4 tree (also called a 2–4 tree) is a self-balancing data structure that is commonly used to implement dictionaries. The numbers mean a tree where every node with children (internal node) has either two, three, or four child nodes:

a 2-node has one data element, and if internal has two child nodes;

a 3-node has two data elements, and if internal has three child nodes;

a 4-node has three data elements, and if internal has four child nodes.

可以看到其实他只是一种表达方式,根据需要进行这样的表达,他是一种B-tree,只不过加上了限定子节点的可以拥有的数量以及一个节点可以拥有元素的数量。

我们定义B-tree的时候一般都是说order m,也就是度为m的B-tree。

According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:

Every node has at most m children.

Every non-leaf node (except root) has at least ⌈m⁄2⌉ children.

The root has at least two children if it is not a leaf node.

A non-leaf node with k children contains k−1 keys.

All leaves appear in the same level

学习B-Tree其实主要是在面试的时候被问到数据库索引,而当一涉及到想要建立所以就是扯出了一大堆B-tree的变种,出发点都相同,减少磁盘的机械运动时间。