下沙经济开发区建设局网站,有哪些做外贸的网站,中国建筑网官网总公司,站内推广途径B 树是为了磁盘或其它存储设备而设计的一种多叉#xff08;下面你会看到#xff0c;相对于二叉#xff0c;B树每个内结点有多个分支#xff0c;即多叉#xff09;平衡查找树。
B 树又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下#xff1a;
树中每个结点最多含…B 树是为了磁盘或其它存储设备而设计的一种多叉下面你会看到相对于二叉B树每个内结点有多个分支即多叉平衡查找树。
B 树又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下
树中每个结点最多含有m个孩子m2除根结点和叶子结点外其它每个结点至少有[ceil(m / 2)]个孩子其中ceil(x)是一个取上限的函数若根结点不是叶子结点则至少有2个孩子特殊情况没有孩子的根结点即根结点为叶子结点整棵树只有一个根节点所有叶子结点都出现在同一层叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点实际上这些结点不存在指向这些结点的指针都为null)每个非终端结点中包含有n个关键字信息 (P1K1P2K2P3......KnPn1)。其中a) Ki (i1...n)为关键字且关键字按顺序升序排序K(i-1) Ki。 b) Pi为指向子树根的接点且指针P(i)指向子树种所有结点的关键字均小于Ki但都大于K(i-1)。 c) 关键字的个数n必须满足 [ceil(m / 2)-1] n m-1。 来模拟下查找文件29的过程 (1) 根据根结点指针找到文件目录的根磁盘块1将其中的信息导入内存。【磁盘IO操作1次】 (2) 此时内存中有两个文件名1735和三个存储其他磁盘页面地址的数据。根据算法我们发现172935因此我们找到指针p2。 (3) 根据p2指针我们定位到磁盘块3并将其中的信息导入内存。【磁盘IO操作2次】 (4) 此时内存中有两个文件名2630和三个存储其他磁盘页面地址的数据。根据算法我们发现262930因此我们找到指针p2。 (5) 根据p2指针我们定位到磁盘块8并将其中的信息导入内存。【磁盘IO操作3次】 (6) 此时内存中有两个文件名2829。根据算法我们查找到文件29并定位了该文件内存的磁盘地址。
插入操作
生 成从空树开始逐个插入关键字。但是由于B_树节点关键字必须大于等于[ceil(m/2)-1],所以每次插入一个关键字不是在树中添加一个叶子结点 而是首先在最底层的某个非终端节点中添加一个“关键字”该结点的关键字不超过m-1,则插入完成否则要产生结点的“分裂”将一半数量的关键字元素分裂到新的其相邻右结点中中间关键字元素上移到父结点中。 1、咱们通过一个实例来逐步讲解下。插入以下字符字母到一棵空的B 树中非根结点关键字数小了小于2个就合并大了超过4个就分裂C N G A H E K Q M F W L T Z D P R X Y S首先结点空间足够4个字母插入相同的结点中如下图
2、当咱们试着插入H时结点发现空间不够以致将其分裂成2个结点移动中间元素G上移到新的根结点中在实现过程中咱们把A和C留在当前结点中而H和N放置新的其右邻居结点中。如下图
3、当咱们插入E,K,Q时不需要任何分裂操作 4、插入M需要一次分裂注意M恰好是中间关键字元素以致向上移到父节点中
5、插入F,W,L,T不需要任何分裂操作
6、插入Z时最右的叶子结点空间满了需要进行分裂操作中间元素T上移到父节点中注意通过上移中间元素树最终还是保持平衡分裂结果的结点存在2个关键字元素。
7、插入D时导致最左边的叶子结点被分裂D恰好也是中间元素上移到父节点中然后字母P,R,X,Y陆续插入不需要任何分裂操作别忘了树中至多5个孩子。
8、最后当插入S时含有N,P,Q,R的结点需要分裂把中间元素Q上移到父节点中但是情况来了父节点中空间已经满了所以也要进行分裂将父节点中的中间元素M上移到新形成的根结点中注意以前在父节点中的第三个指针在修改后包括D和G节点中。这样具体插入操作的完成。
