- 论坛徽章:
- 0
|
|
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树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
在二叉查找树中进行查找的方法可以归纳为“自顶向下，左小右大”。
假设我们想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。我们的目标就是设计一个简单的方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方，因为对于我们的假设来说，这个条目很快就被再次查找的可能性极大。
之前存在两种重构方法：
1、单旋：在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边。（除非x就是树根）
2、搬移至树根：在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边，然后重复这个操作直至x成为树根。
splay树的重构方法和搬移至树根的方法相似，它也会沿着查找路径做自底向上的旋转，将被查找条目移至树根。但不同的是，它的旋转是成对进行的，顺序取决于查找路径的结构。为了在节点x处对树进行splay操作，我们需要重复下面的步骤，直至x成为树根为止：
1、第一种情况：如果x的父节点p(x)是树根，则旋转连接x和p(x)的边。（这种情况是最后一步）
2、第二种情况：如果p(x)不是树根，而且x和p(x)本身都是左孩子或者都是右孩子，，则先旋转连接p(x)和x的祖父节点g(x)的边，然后再旋转连接x和p(x)的边。
3、第三种情况：如果p(x)不是树根，而且x是左孩子，p(x)是右孩子，或者相反，则先旋转连接x和p(x)的边，再旋转连接x和新的p(x)的边。
在节点x处进行splay操作的时间是和查找x所需的时间成比例的。splay操作不单是把x搬移到了树根，而且还把查找路径上的每个节点的深度都大致减掉了一半。这种减半效应使得splay树更有效率，这是其它的简单的重构方法所不具备的特性。
splay树的更新操作：
access(i, t):如果i在树t中，则返回指向它的指针，否则返回空指针。
insert(i, t):将条目i插入树t中（假设其尚不存在）。
delete(i, t):从树t中删除条目i（假设其已经存在）。
join(t1, t2):将树t1和t2合并成一棵树，其中包含之前两棵树的所有条目，并返回合并之后的树。这个操作假设t1中的所有条目都小于t2中的条目，操作完成之后会销毁t1和t2。
split(i, t):构建并返回两棵树t1和t2，其中t1包含t中所有小于等于i的条目，t2包含t中所有大于i的条目。操作完成之后销毁t。
为了实现access(i, t)，我们可以从树t的根部向下查找i。如果查找操作遇到了一个含有i的节点x，我们就在x处进行splay操作，并返回指向x的指针，访问结束。如果遇到了空指针，表示i不在树中，我们就在最后一个非空节点处进行splay操作，然后返回空指针。如果树是空的，我们将忽略掉splay操作。
为了实现join(t1, t2)，我们首先访问t1中最大的条目i。访问结束之后，t1的根节点中包含的就是i，它的右孩子显然为空。我们把t2作为这个根节点的右子树并返回完成之后的新树即可实现join操作。
为了实现split(i, t)，我们首先执行access(i, t)，然后根据新的根节点中的值是大于还是小于等于i来切断这个根节点的左链接或右链接，并返回形成的两棵树。
为了实现insert(i, t)，我们首先执行split(i, t)，然后把t换成一个由新的包含有i的根节点组成的树，这个根节点的左右子树分别是split返回的树t1和t2。
为了实现delete(i, t)，我们首先执行access(i, t)，然后把t换成其左子树和右子树join之后的新树。
下面的实现insert和delete的方法有更好的摊平时间上限：
insert(i, t):查找i，把遇到的空指针替换成一个含有i的新节点，然后再在新节点处对树进行splay操作。
delete(i, t):查找含有i的节点，设此节点为x，其父节点为y。把x的左右子树合并之后替换掉x，然后再从y处进行splay操作。
下面根据作者给出的例程中的数据，画了一些简单的示意图，以期给出一个splay树的形象化说明。（由于FreeBSD根据自己的需要对算法进行了修改，因此这些图并不适于描述FreeBSD虚存系统中splay树的操作过程）
刚开始树中只有一个节点，键值为0。现在向树中添加键值为541的节点。（作者例程中的添加算法基本上可以归纳为上面给出的第二种insert算法，因此会先有一个根据新键值splay的过程，然后才是添加新键值并再次splay的操作）这里由于原先树中只有一个节点，因此插入之前的splay操作不会有任何效果。
插入键值为58的节点：
插入键值为599的节点：
插入键值为116的节点：
插入键值为657的节点：
[ 本帖最后由 雨丝风片 于 2006-3-15 21:28 编辑 ] |
|
免费注册
发表于 2006-03-15 14:24
发表于 2006-03-15 14:43
