4、B-树

　　(图d)

　　B-树是一种平衡多路查找树，它在文件系统中很有用。一棵m阶B-树(图d为4阶B-树)，具有下列性质：

　　(1)树中每个节点至多有m棵子树;

　　(2)若根节点不是叶子节点，则至少有2棵子树;

　　(4)每个节点中的信息结构为(A0,K1,A1,K2......Kn,An)，其中n表示关键字个数，Ki为关键字，Ai为指针;

　　(5)所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。

　　5、B+树

　　(图e)

　　B+数是B-树的一种变形，它与B-树的差别在于(图e为3阶B+树)：

　　(1)有n棵子树的节点含有n个关键字;

　　(2)所有的叶子节点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子节点本身按关键字大小自小到大顺序链接;

　　(3)所有非终端节点可以看成是索引部分，节点中仅含有其子树(根节点)中最大(或最小)关键字，所有B+树更像一个索引顺序表;

　　(4)对B+树进行查找运算，一是从最小关键字起进行顺序查找，二是从根节点开始，进行随机查找。

添加您的专属公考咨询师

扫码免费领取专属学习礼包

领取资料 咨询优惠