云服务器可以做几个网站,最新的军事新闻报道,企业备案域名,seo优化软件哪个最好用B树#xff1a; m阶B树的核心特性#xff1a;
树中每个节点至多有m棵子树#xff0c;即至多含有m-1个关键字根节点的子树数属于[2, m]#xff0c;关键字数属于[1, m-1]#xff0c;其他节点的子树数属于 [ ⌈ m 2 ⌉ , m ] [\lceil \frac{m}{2}\rceil, m] [⌈2m⌉,m] m阶B树的核心特性
树中每个节点至多有m棵子树即至多含有m-1个关键字根节点的子树数属于[2, m]关键字数属于[1, m-1]其他节点的子树数属于 [ ⌈ m 2 ⌉ , m ] [\lceil \frac{m}{2}\rceil, m] [⌈2m⌉,m]关键字数属于 [ ⌈ m 2 ⌉ − 1 , m − 1 ] [\lceil \frac{m}{2}\rceil-1, m-1] [⌈2m⌉−1,m−1]对任一节点其所有子树高度都相同关键字的值子树0关键字1子树1关键字2…类比二叉查找树 左根右所有叶节点都出现在同一层次上且不带信息可以视为外部节点或类似于折半查找判定树的查找失败节点实际上这些节点不存在指向这些节点的指针为空
B树 m阶B树的核心特性
通常在B树上有两个头指针一个指向根节点另一个指向关键字最小的叶子节点。因此可对B树进行两种查找运算一种是从最小关键字起顺序查找另一种是从根节点开始进行随机查找树中每个节点至多有m棵子树节点的子树个数与关键字个数相等根节点的子树数属于[2, m]其他节点的子树数属于 [ ⌈ m 2 ⌉ , m ] [\lceil \frac{m}{2}\rceil, m] [⌈2m⌉,m]节点的子树个数与关键字个数相等所有叶节点包含全部关键字及指向相应记录的指针叶节点中将关键字按大小顺序排列并且相邻叶节点按大小顺序相互链接起来支持顺序查找所有分支节点中仅包含它的各个子节点中关键字的最大值及指向其子节点的指针B树中无论查找成功与否最终一定都要走到最下面一层节点对比B树的查找查找成功情况下可能停在任何一层B树中非叶节点不含有该关键字对应记录的存储地址因此可以使一个磁盘块包含更多个关键字使得B树的阶更大树高更矮读磁盘次数更少查找更快。典型应用如关系型数据库的“索引”如MySQL
二者对比
-B树B树关键字数与子树数节点中的n个关键字对应n1棵子树节点中的n个关键字对应n棵子树节点的关键字数范围根节点的关键字数[1, m-1]其他节点的关键字数[ ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil ⌈2m⌉-1, m-1]根节点的关键字数[1, m]其他节点的关键字数[ ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil ⌈2m⌉, m]节点重复性各节点中包含的关键字是不重复的叶节点包含全部关键字非叶节点中出现过的关键字也会出现在叶节点中节点的作用B树的节点中都包含了关键字对应的记录的存储地址叶节点包含信息所有非叶节点仅起索引作用非叶节点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针来源m阶B树是二叉查找树的进化m阶B树是分块查找的进化进化为多级分块查找查找方式不支持顺序查找查找成功时可能停在任何一层节点查找速度不稳定支持顺序查找查找成功或失败都会到达最下一层节点查找速度稳定
相同点
除根节点外都最少 ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil ⌈2m⌉个分叉确保节点不要太空任何一个节点的子树都一样高确保“绝对平衡”二者都是用于文件系统 B树主要用作文件的索引因此它的查找涉及外存的存取。具体来讲在B树上进行查找包含两种基本操作 1在B树中找节点由于B树通常存储在磁盘上因此查找操作1是在磁盘上进行的2在节点中找关键字这一查找操作是在内存中进行的即在磁盘上找到指针p所指节点后先将节点中的信息读入内存然后再利用顺序查找或折半查找查询等于K的关键字显然在磁盘上进行一次查找比在内存中进行一次查找耗费时间更多因此在磁盘上进行查找的次数即待查关键字所在节点在B树上的层次数是决定B树查找效率的首要因素 B树是应文件系统所需而出的一种B树的变型树
