查找概论4-多路查找树查找概论4-多路查找树

【查找概论4-多路查找树】由于内存大小有限，需要将数据存储在硬盘中，这时对数据的处理需要不断的从存储设备中调入调出内存页面。此时处理的时间复杂度的计算就会发生变化，需要额外考虑访问外部存储设备的时间以及访问次数
在大量数据时候，树的单一数据元素节点将会导致树的度很大或者树的高度很大，因此需要打破每个一个树节点存储一个元素的限制，引入了多路查找树

多路查找树：每一个节点的孩子树可以多于两个，且每一个节点处可以存储多个元素。典型的有2-3树，2-3-4树，B树，B+树

2-3树

定义：包含两种节点，2节点和3节点，2节点有一个数据元素和2个孩子，3节点有两个数据元素和3个孩子
特别说明，2、3节点要么没有孩子要么就有2、3个孩子
2-3树的所有叶子在同一层次，并且依旧是一颗排序树
2-3树复杂在于节点的插入和删除需要满足上述条件

2-3-4树

2-3-4树是2-3树的扩展，包含一个4节点，4节点有3个数据元素和4个孩子，其他和2-3树一致

B树

B树是一种平衡的多路查找树，2-3树2-3-4树都是B树的特例，节点最大的孩子树称为B树的阶
一颗m阶的B树有如下性质
如果根节点不是叶子节点，则其至少有两颗子树
每个非根的分支节点都有k-1个元素和k个孩子，每一个叶子节点都有k-1个元素，其中向上取整[m/2]<=k<=m。
所以叶子位于同一层次
所以分支节点包含下列信息（n A0 K1 A1 K2......Kn An）,即n个元素和n+1个孩子节点的指针。
下面这个图感觉有点问题，即中间那个分支节点的孩子树？，不过大家都以这个图为例。。。。。

文章图片
QQ截图20140809141302.jpg

B+树

B树还是有缺陷的在B树中如果要遍历每一个元素，则会导致一个节点被访问多次，即不停的在内存和外部存储器之间不断地切换，为了解决所有元素遍历的基本问题，在B树原有的基础上加入了新的元素组织方式，形成B+树
B+树是应文件系统所需的一种B树的变形树
B+树中，出现在分支节点的的元素会被当做该分支节点在中序遍历的位置在叶子节点中再次列出
B+树中，每一个叶子节点都保存一个指向后一个叶子节点的指针

文章图片
QQ图片20140809140353.jpg