B-Tree的定义1B-Tree算法刨根问底算法ContentsB-Tree的定义 ......................................................................................... 1对应关系算法复杂度 ............................................................................................. 2B-tree算法实现 ....................................................................................... 4操作操作节点的分裂节点插入过程抢占式分裂（）创建一个空的删除操作B-Tree变种 ............................................................................................ 8区别于二叉树是一种平衡多叉搜索树。B-Tree的定义根据的定义，阶的有如下的特性：节点左边的元素都比它小，节点右边的元素都比它大每个节点最多有个子节点除了根节点之外，非叶节点（没有孩子的节点）至少有个子节点如果根节点不是叶子节点则其至少有两个子节点包含个子节点的节点共有个键所有的叶子节点的高度相同一般表示有两种表示方法：Kuath: B-Tree of Order 其中表示每一个节点中至多有5个子节点；则有如下的特性：CLRS: B-Tree of min degree 而则定义了一个节点中至少有5个子节点 算法复杂度2这里指的是一个节点中子节点的数目。中用的最小度，即节点中最少有多少个子节点。例如即表示的是，每个子节点中可以有、或者个。CS673: B-tree of maximum degree k而也有使用的，例如里面，使用的就是最大度（即最多有个子节点），则：所有的最少有个，最多有个树即对应到对应关系这些表示方法的对应关系如下：可见实际等价于。算法复杂度根据的定义（，如果的高度为考虑最少含有多少个则当：节点包含个其他所有节点有且仅有有个这种场景时，所包含的最少： 算法复杂度3设为第层的节点数，容易看出当时，当时，当时，当时，从开始，每一层的数目即，根据等比数列求和公式即可算出总的数目为：设为的所有数，则有：可以得：其算法时间和空间复杂度如下：平均最坏空间复杂度查找插入删除 B-tree算法实现4B-tree算法实现search操作根据的定义，左边的都比其小，右边皆比其大，则不应该存在重复的。查找算法类似于叉树的查找，步骤如下：从根节点开始，依次同节点中进行比较，如果大于或者等于则停止如果找到相等的，则停止搜索如果没有找到，则到下一级节点中进行查找；如果已经是叶子节点，则查找结束在中查找通常当较小时，我们在节点中查找的时候只需要进行顺序查找即可；如果较大的情况下，可以进行二分查找提高搜索的效率。B-TREE-SEARCH(x, k) i ← 1 while i ≤ n[x] and k ≥ key[x, i] do i ← i + 1 if i ≤ n[x] and k = key[x, i] then return (x, i) if leaf[x] then return NIL else c = DISK-READ(c[x, i]) return B-TREE-SEARCH(c, k)insert操作节点的分裂在进行之前，需要考虑的就是，规定了一个节点中最大的的数目，当一个节点中子节点的数目超过允许的最大值的时候，需要将节点拆分为两个。例如上面的例子，如果再插入的话，如果直接插入则子元素已经超出了最大允许的数目： B-tree算法实现5在中插入在上面的例子中，拆分之后，两个子节点的元素个数正好是平均的，但是，如果为偶数的情况下是不平均的：在中插入值得注意的是，因为每次分裂高度会增加，同时会增加父元素的个数，那么也可能导致父节点满。所以如果上层节点也满了的话，也是需要递归的分裂的：在中插入节点插入过程当为奇数时，插入的过程如下： B-tree算法实现6当为偶数时，插入的过程如下：在的过程中，一般的做法是先将元素插入到叶节点，这时候如果发现叶节点满了，需要将其，并将其中一个提升到父节点中。同时，需要看父节点是否满，如果满了也需要进行拆分，直到根节点。但是这种做法需要插入后再回溯，比较难以实现。另一种方式则是在插入的过程中，一旦发现节点已经满了，无法再容纳元素，则先将其拆分，然后再继续朝下查找。这样只需要查找一次，再最后插入到叶子节点的时候，能够保证不会溢出。 B-tree算法实现7抢占式分裂（Preemtive Split）如上所说，在操作的时候，是先插入元素，然后再进行拆分的，这样可能插入之后还需要一直递归到上层节点进行拆分。例如下面的一个场景：而正是在之前即进行拆分，当发现一个节点快要满了的时候，就先之后再插入，自顶向下，不需要再回溯到上一层的节点。从上面的例子可以看到，两种方式构造出的在插入之后其实是不大一样的，而当插入之后则变成一致了。创建一个空的B-treeB-TREE-CREATE(T) x ← ALLOCATE-NODE() leaf[x] ← TRUE n[n] ← 0 DISK-WRITE(x) root[T] ← x B-Tree变种8删除操作B-Tree变种树：为的又被称之为每个非叶子节点有个、个或者个子节点树：为的又被称之为每个非叶子节点有个或者个子节点：：参考资料