数据结构 B树、B-树
——B树
B树即 Balance tree 也就是平衡树,它是在搜索树的基础上,维持每一个节点的左右子树高度之差不超过1的结构,使得搜索的平均时间复杂度为O(log N)级别。
——二叉搜索树
对于任何一个节点N,其左边子树的所有节点值小于N 其右边子树的所有节点的值大于N
给点一个查询值,从根节点值开始,一次判断当前节点的值和查询值的大小关系,选择进入左子树或右子树
——B-树
一颗M=3的B-树
本质是多路搜索树,所有序列关键值分布在整颗树中。每个非叶子节点包含 关键字序列 和指向下一分层区间节点的指针
- 定义任意非叶子结点最多只有M个儿子;且M>2;
- 根结点的儿子数为[2, M],除根结点以外的非叶子结点的儿子数为[M/2, M];
- (非叶子节点至少含M/2个儿子,确保避免出现退化成类似链表形式,相当于确保了树的整体高度控制在O(logN)级别)
- 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
- 非叶子结点的关键字个数=指向儿子的指针个数-1(即关键字作为划分区间边界值)
- 非叶子结点的关键字按照从左向右升序所有叶子结点位于同一层;
搜索过程:
- 从根节点开始,由于每个节点包含一个不大于M的递增序列,做一次二分查找
- 若查找到该值,那么查找结束,否则根据查找边界进入下一层区间
- 直到叶子节点也没有查找到,那么查找失败