2.4 Free list行为

2.4.1 Freelist Link and Unlink 操作

Freelist 按后进先出队列(LIFO) 方式管理。也就是说最后被link到freelist的块拥有最先unlink的机会。当块中空闲空间增加到大于PCTFREE时，块放入freelist中。free list中的块可用来作update 或insert。 当块中没有足够的空间用于insert操作时并且使用空间大于PCTUSED，块就会从free list中移出。

在块在DELETE or UPDATE 操作之后，如果使用空间落到PCTUSED下，块再次link到free list中。每次块加入free list时，都是link到链表的头部。

例如:考虑段中有120个块编号由1到120。其中有6个块在free list上并假设HWM是 80。(block实际使用DBA编号)

10->24->45->46->65->80-|

现在作INSERT 操作,需要400 bytes空间。假设块10上空间不足，但块24上空间可用。现在数据插入到块 24 ，现在块24的剩余空间小于该表的PCTUSED。因此块 24 从free list链表中移出。PCTFREE and PCTUSED参数的目的就是用来控制数据块从free list的链表中移入/移出行为的。现在free lists象这样:

10->45->46->65->80-|

然后在同一事务中作DELETE同一个段的数据，使块 54 和 67落到PCTUSED下。现在这些块加入到free list链中。free list链现在象这样:

67->54->10->45->46->65->80-|

2.4.2 Transaction Free List 算法

扫描segment Header块中所有的Tx free list,检查是否还没有Tx free list entry分配给transaction， 如何没有，将寻找未使用的entry或已经提交了事务的空的Tx free list。如果上述搜索过程失败, 新的entry会在segment Header块中Tx free lists区域中开辟。如果没有空间来生成, 事务就必须等待entry的释放。

segment header中的最大free list个数:

Block Size Max # Freelists

----------- -----------------

2K 24

4K 50

8K 101

16k 204

事务T1释放出来的空闲块(DELETE or UPDATE)的使用 :

l 立即被T1所重用