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 的order

[树 的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).

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.

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的变种，出发点都相同，减少磁盘的机械运动时间。