B树的一些性质
B树的一些性质
小泽玛丽罗 发表于2年前
B树的一些性质
  • 发表于 2年前
  • 阅读 9
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

B树

为什么会有B树: 因为二叉树的查找平均时间是logN,是与二叉树的深度有关,所以为了减少二叉树的深度,增加查找速度,势必要增加树的叉树。如果该树是M叉的,M>2的话,logm(N)势必要小于log2(N),所以当数据量非常大的时候,B树的平均查找时间要少于二叉树。

(1)B树的性质

  • 数据项是存储在叶子节点上的
  • 根结点的儿子树,在[2,M]之间,M指的是树的阶数,就是有几叉
  • 除根结点外,所有非叶子结点的儿子树在M/2(这里要向上取整,2.2取3,但是有些地方好像是不向上取整的)到M之间,例如如果是5阶的B树,那么非叶子结点的儿子树在3~5之间
  • 在叶子结点上,每个叶子结点包含的数据项在L/2(向上取整)到L之间,这里的L一般和M是相等的,但不是必须相等的

下面盗来一幅图片,画的是3阶的B树

 

B树的其他特性:

  • 关键字即搜索的信息集合分布在整颗树中;
  • 任何一个关键字出现且只出现一次,减少不必要的重复
  • 搜索有可能在非叶子结点结束,如果搜索26,那么在就可以直接在非叶子结点返回了;
  • 当关键字的数量大于L时,就要进行分裂,在父节点上添加关键字,如果父节点的关键字也超过了L,那就继续往上,知道根节点位置,这是唯一增加B树深度的办法。(这里L 一般和M相同)
  • 当删除关键字的时候,如果数量小于L/2

(还没写完,先做个笔记)

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 7
博文 57
码字总数 17545
×
小泽玛丽罗
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: