数据结构 B树、B-树

——B树

B树即 Balance tree 也就是平衡树,它是在搜索树的基础上,维持每一个节点的左右子树高度之差不超过1的结构,使得搜索的平均时间复杂度为O(log N)级别。

——二叉搜索树

数据结构 B树、B-树

对于任何一个节点N,其左边子树的所有节点值小于N 其右边子树的所有节点的值大于N

给点一个查询值,从根节点值开始,一次判断当前节点的值和查询值的大小关系,选择进入左子树或右子树

——B-树

一颗M=3的B-树

数据结构 B树、B-树

本质是多路搜索树,所有序列关键值分布在整颗树中。每个非叶子节点包含 关键字序列  和指向下一分层区间节点的指针

  • 定义任意非叶子结点最多只有M个儿子;且M>2;
  • 根结点的儿子数为[2, M],除根结点以外的非叶子结点的儿子数为[M/2, M];
  • (非叶子节点至少含M/2个儿子,确保避免出现退化成类似链表形式,相当于确保了树的整体高度控制在O(logN)级别)
  • 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
  • 非叶子结点的关键字个数=指向儿子的指针个数-1(即关键字作为划分区间边界值)
  • 非叶子结点的关键字按照从左向右升序所有叶子结点位于同一层;

搜索过程:

  • 从根节点开始,由于每个节点包含一个不大于M的递增序列,做一次二分查找
  • 若查找到该值,那么查找结束,否则根据查找边界进入下一层区间
  • 直到叶子节点也没有查找到,那么查找失败