InnoDB Index Page Parsing

The file header describes some general information applicable to various types of pages, as shown in the table below.

The following describes several important components:

• FIL_PAGE_OFFSET: page number of the current page, indicating the logical offset of the page in the data file.
• FIL_PAGE_PREV and FIL_PAGE_NEXT: store the page numbers of the previous and next pages, respectively. They connect physically discontinuous pages into logically adjacent pages at the same level of the B+ tree. On page 0 of the tablespace, these two fields are reloaded as FIL_PAGE_SRV_VERSION and FIL_PAGE_SPACE_VERSION.

  On one hand, large tables struggle to acquire contiguous space at a time and can only be allocated in chunks. On the other hand, frequent page splits and reclaims cause logically adjacent pages to drift far apart on the disk. These two pointers are used to maintain a linked list structure that keeps indexes ordered at the logical level, allowing queries to quickly jump between physically non-contiguous pages.

• FIL_PAGE_LSN: LSN corresponding to the latest modification of the current data page. The idempotence of redo logs depends on this field. During crash recovery, if the LSN of a redo log is less than or equal to this value, the redo log is not applied.

Infimum and Supremum Records

These are two pseudo-records. In the DYNAMIC row format, each record consists of a 5-byte record header and an 8-byte fixed meaning. Since these two records are not user data, they are stored separately in the Infimum + Supremum section.

In TaurusDB, the infimum record is the logically smallest record on the data page, and all user records are greater than it. The supremum record is the largest record on the data page, and all user records are smaller than it. These two records are generated when the data page is created and cannot be deleted.

Figure 2 Infimum and supremum records

All user records are stored here in row format. When a page is generated for the first time, this section is empty. Each time a record is inserted, the corresponding space is allocated from the free space to the user records. By default, there is no gap between records. However, if the space from deleted records is reused, space fragmentation may occur.

Records are sorted on the page in the order they are inserted. Each record contains a pointer (next_record) to the next record, forming a singly linked list. You can traverse the page starting from the infimum record through to the supremum record. In a clustered index, records are stored in primary key order. In a secondary index, records are sorted by index key and primary key.

User records include all active records and all deleted records (marked as delete_marked). Records that have been physically deleted via purge are moved to the PAGE_FREE list and are no longer accessible.

Figure 3 User records

The space between PAGE_HEAP_TOP and the last page directory is free space, which is reset to 0. When you need to insert a record, the system first attempts to find available space among the previously deleted records. If no suitable space is found, the system allocates space from here. After space is allocated to a record, the values of PAGE_N_RECS and PAGE_N_HEAP need to be incremented.

To accelerate the query efficiency within a page and avoid traversing the single-linked list for each query, TaurusDB divides all valid records (including infimum and supremum records, but excluding deleted records) on the page into several groups for management. Records that are marked as deleted but have not been physically deleted via purge are still retained in the page directory and continue to be linked to the next_record logical linked list for subsequent unified cleanup.

• The last record in each group (that is, the largest record in the group) is used as the owner_rec, and its n_owned field stores the number of records in the group.
• The address offsets of the owner_rec are collected in index order to form the page directory, which is stored at the end of the page and grows from higher addresses toward lower addresses.

This section is located at the very end of the data page and occupies only 8 bytes. The first four bytes represent the checksum of the page, and the last four bytes store the four least significant bytes of FIL_PAGE_LSN.