FreeBSD虚存系统splay树的基本原理

[/url]

FreeBSD虚存系统splay树的基本原理
雨丝风片:chinaunix.net
在FreeBSD的虚拟内存系统中，一个虚拟地址空间中的不同区域是由很多的vm_map_entry结构体来描述的，这些vm_map_entry结构体同时按两种方式进行组织，一种是双向链表，一种是splay树。关于splay树的设计原理，请参见原始作者Daniel Dominic Sleator和Robert Endre Tarjan的论文【Self-Adjusting Binary Search Trees】。这里先给出我阅读后的一些笔记和简单的原理图示。由于FreeBSD虚拟内存系统中的splay树的节点是用来存储虚拟地址空间中一段区域的起始和终止地址等其它相关信息的，因此它在原有splay树的基础上进行了一些修改，以更快地满足内存区域匹配的要求。稍后将另写文章，结合FreeBSD6.0的源代码对此加以分析。
FreeBSD虚存系统的相关原理及图示请参见【The Design and Implementation of the FreeBSD Operating System】的第5章。
splay树在二叉查找树中引入了摊平复杂度和自调整的概念。
其它查找树的不足：
1、平衡树：对于一个有n个节点的平衡树，最坏情况下每次查找的时间不会超过O(log n)，但是，如果访问模式不均匀，平衡树的效率就会受到影响。此外，它们还需要额外的空间来存储平衡信息。
2、最优查找树：保证了最小的平均查找时间。但它需要假定查找概率是固定的和已知的，并且访问之间不能有相关性。它们的插入和删除开销都非常高。
3、倾斜查找树：结合了最优查找树的快速平均访问时间和平衡树的快速更新能力，但其结构上的限制更为复杂，和平衡树比起来也更难维护。
4、Finger查找树：可以在一个或多个临近的“手指”中进行快速访问，但需要在每个节点中存储额外的指针。
这些树的设计目标都是减少最坏情况下每次操作的时间，但是查找树的典型应用并不是只查一次就够了，经常是需要执行一系列的查找操作，因此我们应当主要关心这一系列的操作所花费的总体时间，而不只是每次操作单独花费的时间。对于此类应用，更好的目标就是降低操作的摊平时间，此处的摊平时间是指在一系列最坏情况的操作序列中的一次操作的平均时间。
获得摊平效率的一种方法就是使用“自调整”的数据结构。我们允许结构处于任何状态，但在每次操作期间都会应用一个简单的重构规则，以期提高未来操作的效率。其实在其它的数据结构中也有这种通过重构来获得摊平效率的例子，比如线性链表的前移和平衡树上的路径压缩。
和平衡的或是其它对结构有明确限制的数据结构比起来，自调整数据结构有以下几个优点：
1、从摊平角度而言，忽略常量因子，它们绝对不会比有明确限制的数据结构差，而且由于它们可以根据使用情况进行调整，在使用模式不均匀的情况下会更加有效。
2、由于无需存储平衡或者其它的限制信息，它们所需的空间更小。
3、它们的查找和更新算法概念简单，易于实现。
自调整结构有两个潜在的缺点：
1、它们需要更多的局部调整，尤其是在查找期间。（那些有明确限制的数据结构仅需在更新期间进行调整，查找期间则不用）
2、一系列查找操作中的某一个可能会耗时较长，这在实时应用程序中可能是个不足之处。
splay树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
在二叉查找树中进行查找的方法可以归纳为“自顶向下，左小右大”。
假设我们想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。我们的目标就是设计一个简单的方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方，因为对于我们的假设来说，这个条目很快就被再次查找的可能性极大。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有