Everyday Life

Friday, October 16, 2009

B树和B+树的些微区别

实现树型目录结构文件系统，常采用二叉树，其中每个节点都有父指针，子指针和兄弟指针，其中子指针指向该目录下的第一个子节点，而该子节点的父指针则指向它的上级目录。目录下各子节点用兄弟指针连接起来。大型文件系统一般采用B+树实现，而不采用B树，这时因为：在B树中，分支节点和叶子节点均保存记录的关键码和记录的指针；在B+树中，分支节点只保存记录关键码的复制，无记录指针，所有记录都集中在叶节点一层，并且叶节点可以构成一维线性表，便于连续访问和范围查询。由于在B树的叶子节点中直接就包含记录，导致了叶节点能存放的SearchKey数目减少，同样大的文件相应的需要的节点数目就增多了，树的高度也较B+树深了很多。对于同样阶的B树和B+树，B+树的树高和平均检索长度均大于B树（因为B+树必须检索到叶节点一层）；但实际检索过程中，最耗时间的是I/O，也就是访盘次数越少越好。B+树的分支节点无记录指针，同样一个盘块可以存放的关键码数就更多，所以虽然平均检索长度大，但访盘次数反而少，文件操作的速度也就比B树快。