子记录模式下二叉排序树的算法分析

1 引言在微型计算机文件系统支撑下设计数据处理应用系统时,提高效率的关键在于减少访问外存的次数。当应用系统数据项的大小(字节数)较小时,我们对如何提高效率的策略是在文件的一个逻辑记录中放i个数据项(i表示数据项的个数)。例如在姓名NAME的一个逻辑记录中存放i个姓名,这种方式称为子记录模式(sub-recordmode)。当文件的记录需要按关键字排序时,将文件组织成二叉排序树是一个有效的选择。在子记录模式下如何组织二叉排序树及算法的变化、性能,正是本文所要探讨的问题。