A tree that has grown beyond its first pages keeps two small trees of its own that say which pages it owns and which of those are free. They are space trees: ordinary B+-trees of pages with the space tree flag (0x20), whose entries are extents. A tree whose root header says single extent has no space trees: its pages are the root page and the pages after it, as many as the initial page count.
Extents
The root header's space tree page number is the root of the owned tree; the page after it is the root of the available tree. A leaf entry is an extent:
| Part | Size | Description |
|---|---|---|
| Key | 4 | The number of the extent's last page, most significant byte first. |
| Data | 4 | The number of pages in the extent, so it covers pages (last − count + 1) to last. |
Entries with the defunct flag are left out. The pages a tree owns are the sum of the counts of the owned tree; the free ones are the sum of the available tree. In a catalog of 20 pages that owns pages 4 to 23, for example, the owned tree has one entry with key 23 and count 20.
Counting
function pagesOf(root):
h = rootHeader(root)
if h.extentSpace == 0: return [root .. root + h.initialPages - 1]
owned = extents(h.spaceTreePage)
free = extents(h.spaceTreePage + 1)
return owned, free
Links
Reference
- Extensible Storage Engine (ESE) Database File (EDB) format – space tree pages