数据结构-B树

1.B树的定义

B树就是一棵平衡的多叉查找树

2.B树的作用以及相对于二叉查找树的优势

用于实现快速查找，相对于二叉树，具有更多的分支，更小的高度。查找树的高度决定了查找过程中访问磁盘的次数，而磁盘的访问速度低。由于B树具有更小的高度，因此在查找时对磁盘的访问会大大降低，从而相对于二叉查找树有更高的效率

2.B树的特性

一棵M阶的B树的特性：

1）数据项存储在树叶上

2）非叶子节点存储M-1个关键字，这些关键字用于指示搜索的方向；第i个关键字为第i+1棵子树中最小的关键字

3）树根节点和树叶儿子数在2到M之间，除树根和叶子节点外，其他节点儿子数在M/2 到M 之间

4）所有树叶都在相同深度上并有L/2 到L之间个数据项

每个树节点代表一个磁盘区块，因此根据磁盘区块的大小和所存储项的大小决定M和L的值。假设一个区块为8192个字节，一棵M阶B数非叶子节点有M-1个关键字和M个指向子节点的指针，设每个关键字占用32个字节，每个指针4个字节，则一个非叶子节点占用36M-32字节，这样可以出M=288。设每个记录占用256个字节，则可计算出L=32

M=5, L=5 的B树结构图：

数据结构-B树

原文：https://www.cnblogs.com/liuxuelin/p/14773342.html