Information Technology Reference
In-Depth Information
(924, 3)
...
525
...
924
tuple
(525, 7)
...
...
Fig. 2.2
Representing a long tuple. The original identifier for the record is .924; 3/.Thereisa
forwarding address to .525; 7/
p
0
, which is linked as a sibling of page p and receives half of the tuples from p.In
the latter case, we must find a page p
0
in the heap with enough free space for the
tuple t .
For allocating and deallocating pages of a B-tree, we can keep a
free-page chain
,
where empty index and data pages are linked when they are detached from the
B-tree. A newly allocated page is taken from the chain of free pages, if there is
a page in the chain. Otherwise, the space allocated for the B-tree is extended by
allocating a new contiguous area from disk and using the first page from this new
area.
Another method for managing free space is to keep information on which pages
are free and which are allocated in a
space map
. In this method, the first page
(page 0) of a file is filled by a bit array with e entries, containing the space map
for the e following pages, that is, pages 1;2;:::;e. The value 1 for the i th element
(bit) in the space map denotes that page i is allocated, while 0 means that page i is
free.
The space map can have about 32,000 entries on a 4-kilobyte page. If the file is
larger than this, additional space maps are needed: page e
C
1 is filled by a space
map for the e pages following that page, and so on. New pages can be allocated to
the file in clusters of e (or fewer) pages.
The free space of a heap-structured file can be maintained by a space map where
the entries are approximated: The entries can be, for example, two-bit integers (i.e.,
values 0-3), so that the amount of free space is represented as:
0: the record area of the page is empty, or the page is unformatted.
1: 0-33% of the record area has been filled.
2: 33-66% of the record area has been filled.
3: over 66% of the record area has been filled.
A tuple t to be added to a heap is converted to its internal representation (a record).
The size of the record is counted, and the space maps of the file for r are searched
to find a page where t fits.
