B-（排序）树 Balance Tree

  • 一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。
  • B-树是一种多路搜索树（并不一定是二叉的）
  • M阶树

    一个结点最多有M棵子树

M = 3 三阶B-树

  • 对于每一个结点，最多有三棵子树。

B+树

B+ 树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。 B+ 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。

  • 性质
    1. 有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
    2. 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
    3. 所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。 B+Tree
  • 特性
    1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
    2. 不可能在非叶子结点命中；
    3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
    4. 更适合文件索引系统； MySQL是基于B+树聚集索引组织表

B*树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针； b*Tree

B-树，B+树与B*树的优缺点比较

  • B+树有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了。
  • B树的优势是当你要查找的值恰好处在一个非叶子节点时，查找到该节点就会成功并结束查询，而B+树由于非叶节点只是索引部分，这些节点中只含有其子树中的最大(或最小)关键字，当非终端节点上的关键字等于给点值时，查找并不终止，而是继续向下直到叶子节点。因此在B+树中，无论查找成功与否，都是走了一条从根到叶子节点的路径。
  • B*树分配新结点的概率比B+树要低，空间使用率更高；

引用

  1. B-树，B+树，B*树详解
  2. B-树，B+树与B*树的优缺点比较