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所重用

l 当T1 commit后被其它需要空闲块的事务重用，过程举例如下:

2.5 HMW概念

HIGH WATER MARK代表一个表使用的最大的(top limit)块 。2.1中已经提到HIGH WATER MARK 记录在segment header中，并且在Oracle插入数据时一般增长5个blocks(并非总是5个块，具体参见2.4.2中流程图中HMW增长方式)。

　　segment header block中与HWM相关信息说明如下: EXTENT CONTROL:
Extent Header:: spare1: 0 space2: 0 #extents: 13 #blocks: 1429
last map 0x00000000 #maps: 0 offset: 4128
Highwater:: 0x020004d0 ext#: 12 blk#: 275 ext size: 475
#blocks in seg. hdr’s freelists: 5
#blocks below: 1229
mapblk 0x00000000 offset: 12
Unlocked
==> spare1: this field is no longer used (old inc#, now always 0)
==> space2: this field is no longer used (old ts#, now always 0)
==> #extents: number of extents allocated to segment
==> #blocks: number of blocks allocated to segment

==> last map: address of last extent map block
0 if extent map is entirely in the segment header
==> #maps: number of extent map block
==> offset: offset to end of extent map

==> HWM dba: address of block at highwater mark
==> ext#: HWM extent number relative to segment
==> blk#: HWM block number within extent
==> ext size: HWM extent size (in blocks)
==> #blocks in seg. hdr’s freelists: number of blocks in seg. hdr’s free list
==> #blocks below: number of blocks below HWM
==> mapblk dba: dba of extent map block containing HWM extent
is 0 if HWM is in the segment header
==> offset: offset within extent map block
is the ext# if HWM is in segment header
==> Locked by: if locked by a transaction, the xid is displayed

HWM可以说是已经使用过的存储空间和未使用过的存储空间之间的分界线。在表使用过程中，HWM一直向一个方向移动，插入记录时HWM可能会向增加的方向移动，但是删除记录时HWM并不会向相反的方向移动。参见2.4.2。下图显示了某个数据段中HWM的位置情况。

HIGH WATER MARK之所以重要是因为它对全表扫描性能的影响。当实施一个全表扫描时，Oracle会读取所有HIGH WATER MARK下的块即使它们是空块。当HIGH WATER MARK 下有很多unused block时实施全表扫描会增加额外的不必要的I/O。它也会在全局共享区中填充很多很多空块。