写点什么

MySQL 面试题:谈谈 MySQL 索引,B,新鲜出炉的 Java 面试真题集锦我给你们整理出来了

用户头像
极客good
关注
发布于: 刚刚

B 树

即二叉搜索树:


  1. 所有非叶子结点至多拥有两个儿子(Left 和 Right);

  2. 所有结点存储一个关键字;

  3. 非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;


如:


B-树

是一种多路搜索树(并不是二叉的):


  1. 定义任意非叶子结点最多只有 M 个儿子;且 M>2;


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


根结点的儿子数为[2, M];


  1. 除根结点以外的非叶子结点的儿子数为[M/2, M];

  2. 每个结点存放至少 M/2-1(取上整)和至多 M-1 个关键字;(至少 2 个关键字)

  3. 非叶子结点的关键字个数=指向儿子的指针个数-1;

  4. 非叶子结点的关键字:K[1], K[2], …, K[M-1];且 K[i] < K[i+1];

  5. 非叶子结点的指针:P[1], P[2], …, P[M];其中 P[1]指向关键字小于 K[1]的子树,P[M]指向关键字大于 K[M-1]的子树,其它 P[i]指向关键字属于(K[i-1], K[i])的子树;

  6. 所有叶子结点位于同一层;


如:(M=3)



B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;


B-树的特性:


  1. 关键字集合分布在整颗树中;

  2. 任何一个关键字出现且只出现在一个结点中;

  3. 搜索有可能在非叶子结点结束;

  4. 其搜索性能等价于在关键字全集内做一次二分查找;

  5. 自动层次控制;


由于限制了除根结点以外的非叶子结点,至少含有 M/2 个儿子,确保了结点的至少利用率。


所以 B-树的性能总是等价于二分查找(与 M 值无关),也就没有 B 树平衡的问题;


由于 M/2 的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占 M/2 的结点;删除结点时,需将两个不足 M/2 的兄弟结点合并;

B+树

B+树是 B-树的变体,也是一种多路搜索树:


  1. 其定义基本与 B-树同,除了:

  2. 非叶子结点的子树指针与关键字个数相同;

  3. 非叶子结点的子树指针 P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);

  4. 为所有叶子结点增加一个链指针;

  5. 所有关键字都在叶子结点出现;


如:(M=3)



B+的搜索与 B-树也基本相同,区别是 B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;


B+的特性:

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
MySQL面试题:谈谈MySQL 索引,B,新鲜出炉的Java面试真题集锦我给你们整理出来了