Class Innodb::Page::Index
In: lib/innodb/page/index.rb
Parent: Innodb::Page

A specialized class for handling INDEX pages, which contain a portion of the data from exactly one B+tree. These are typically the most common type of page in any database.

The basic structure of an INDEX page is: FIL header, INDEX header, FSEG header, fixed-width system records (infimum and supremum), user records (the actual data) which grow ascending by offset, free space, the page directory which grows descending by offset, and the FIL trailer.

Methods

binary_search_by_directory   directory   directory_slot_for_record   directory_slots   directory_space   dump   each_child_page   each_directory_offset   each_directory_record   each_garbage_record   each_record   each_region   free_space   fseg_header   garbage_offset   header_space   index_id   infimum   leaf?   level   linear_search_from_cursor   make_record_description   max_record   min_record   offset_is_directory_slot?   page_header   pos_directory   pos_fseg_header   pos_index_header   pos_infimum   pos_records   pos_supremum   pos_user_records   record   record_bytes   record_cursor   record_describer   record_describer=   record_fields   record_format   record_header   record_header_compact_additional   record_header_compact_null_bitmap   record_header_compact_variable_lengths_and_externs   record_header_redundant_additional   record_header_redundant_field_end_offsets   record_if_exists   record_is_directory_slot?   record_space   records   root?   size_fseg_header   size_index_header   size_mum_record   size_mum_record_header_additional   size_record_header   supremum   system_record   trailer_space   used_space  

Classes and Modules

Class Innodb::Page::Index::Compressed
Class Innodb::Page::Index::RecordCursor

Constants

RECORD_NEXT_SIZE = 2   The size (in bytes) of the "next" pointer in each record header.
RECORD_REDUNDANT_BITS_SIZE = 4   The size (in bytes) of the bit-packed fields in each record header for "redundant" record format.
RECORD_REDUNDANT_OFF1_OFFSET_MASK = 0x7f   Masks for 1-byte record end-offsets within "redundant" records.
RECORD_REDUNDANT_OFF1_NULL_MASK = 0x80
RECORD_REDUNDANT_OFF2_OFFSET_MASK = 0x3fff   Masks for 2-byte record end-offsets within "redundant" records.
RECORD_REDUNDANT_OFF2_NULL_MASK = 0x8000
RECORD_REDUNDANT_OFF2_EXTERN_MASK = 0x4000
RECORD_COMPACT_BITS_SIZE = 3   The size (in bytes) of the bit-packed fields in each record header for "compact" record format.
RECORD_MAX_N_SYSTEM_FIELDS = 3   Maximum number of fields.
RECORD_MAX_N_FIELDS = 1024 - 1
RECORD_MAX_N_USER_FIELDS = RECORD_MAX_N_FIELDS - RECORD_MAX_N_SYSTEM_FIELDS * 2
PAGE_DIRECTION = { 1 => :left, # Inserts have been in descending order. 2 => :right, # Inserts have been in ascending order. 3 => :same_rec, # Unused by InnoDB. 4 => :same_page, # Unused by InnoDB. 5 => :no_direction, # Inserts have been in random order. }   Page direction values possible in the page_header‘s :direction field.
RECORD_TYPES = { 0 => :conventional, # A normal user record in a leaf page. 1 => :node_pointer, # A node pointer in a non-leaf page. 2 => :infimum, # The system "infimum" record. 3 => :supremum, # The system "supremum" record. }   Record types used in the :type field of the record header.
RECORD_INFO_MIN_REC_FLAG = 1   This record is the minimum record at this level of the B-tree.
RECORD_INFO_DELETED_FLAG = 2   This record has been marked as deleted.
PAGE_DIR_SLOT_SIZE = 2   The size (in bytes) of the record pointers in each page directory slot.
PAGE_DIR_SLOT_MIN_N_OWNED = 4   The minimum number of records "owned" by each record with an entry in the page directory.
PAGE_DIR_SLOT_MAX_N_OWNED = 8   The maximum number of records "owned" by each record with an entry in the page directory.

Public Instance methods

binary_search_by_directory(dir, key)

Search or a record within a single page using the page directory to limit the number of record comparisons required. Once the last page directory entry closest to but not greater than the key is found, fall back to linear search using linear_search_from_cursor to find the closest record whose key is not greater than the desired key. (If an exact match is desired, the returned record must be checked in the same way as the above linear_search_from_cursor function.)

directory()

Return an array of row offsets for all entries in the page directory.

directory_slot_for_record(this_record)

Return the slot number for the page directory entry which "owns" the provided record. This will be either the record itself, or the nearest record with an entry in the directory and a value greater than the record.

directory_slots()

The number of directory slots in use.

directory_space()

The amount of space consumed by the page directory.

dump()

Dump the contents of a page for debugging purposes.

each_child_page() {|rec.child_page_number, rec.key| ...}

Iterate through all child pages of a node (non-leaf) page, which are stored as records with the child page number as the last field in the record.

each_garbage_record() {|rec| ...}

Iterate through all records in the garbage list.

free_space()

Return the amount of free space in the page.

fseg_header()

Return the "fseg" header.

garbage_offset()

A helper function to return the offset to the first free record.

header_space()

The amount of space consumed by the page header.

index_id()

A helper function to return the index id.

infimum()

Return the infimum record on a page.

leaf?()

A helper function to identify leaf index pages.

level()

A helper function to return the page level from the "page" header, for easier access.

linear_search_from_cursor(search_cursor, key)

Search for a record within a single page, and return either a perfect match for the key, or the last record closest to they key but not greater than the key. (If an exact match is desired, compare_key must be used to check if the returned record matches. This makes the function useful for search in both leaf and non-leaf pages.)

make_record_description()

Return a set of field objects that describe the record.

max_record()

Return the maximum record on this page.

min_record()

Return the minimum record on this page.

offset_is_directory_slot?(offset)

Return the slot number of the provided offset in the page directory, or nil if the offset is not present in the page directory.

page_header()

Return the "index" header.

pos_directory()

The position of the page directory, which starts at the "fil" trailer and grows backwards from there.

pos_fseg_header()

Return the byte offset of the start of the "fseg" header, which immediately follows the "index" header.

pos_index_header()

Return the byte offset of the start of the "index" page header, which immediately follows the "fil" header.

pos_infimum()

Return the byte offset of the start of the "origin" of the infimum record, which is always the first record in the singly-linked record chain on any page, and represents a record with a "lower value than any possible user record". The infimum record immediately follows the page header.

pos_records()

Return the byte offset of the start of records within the page (the position immediately after the page header).

pos_supremum()

Return the byte offset of the start of the "origin" of the supremum record, which is always the last record in the singly-linked record chain on any page, and represents a record with a "higher value than any possible user record". The supremum record immediately follows the infimum record.

pos_user_records()

Return the byte offset of the start of the user records in a page, which immediately follows the supremum record.

record(offset)

Parse and return a record at a given offset.

record_bytes()

Return the actual bytes of the portion of the page which is used to store user records (eliminate the headers and trailer from the page).

record_fields()

Returns the (ordered) set of fields that describe records in this page.

record_format()

Return (and cache) the record format provided by an external class.

record_header(cursor)

Return the header from a record.

record_header_compact_additional(header, cursor)

Read additional header information from a compact format record header.

record_header_compact_null_bitmap(cursor)

Return an array indicating which fields are null.

record_header_compact_variable_lengths_and_externs(cursor, nulls)

Return an array containing an array of the length of each variable-length field and an array indicating which fields are stored externally.

record_header_redundant_additional(header, cursor)

Read additional header information from a redundant format record header.

record_header_redundant_field_end_offsets(header, cursor)

Read field end offsets from the provided cursor for each field as counted by n_fields.

record_is_directory_slot?(this_record)

Return the slot number of the provided record in the page directory, or nil if the record is not present in the page directory.

record_space()

Return the amount of space occupied by records in the page.

records()

A helper function to return the number of records.

root?()

A helper function to identify root index pages; they must be the only pages at their level.

size_fseg_header()

The size of the "fseg" header.

size_index_header()

The size of the "index" header.

size_mum_record()

The size of the data from the supremum or infimum records.

size_mum_record_header_additional()

The size of the additional data structures in the header of the system records, which is just 1 byte in redundant format to store the offset of the end of the field. This is needed specifically here since we need to be able to calculate the fixed positions of these system records.

size_record_header()

Return the size of the header for each record.

supremum()

Return the supremum record on a page.

system_record(offset)

Parse and return simple fixed-format system records, such as InnoDB‘s internal infimum and supremum records.

trailer_space()

The amount of space consumed by the trailers in the page.

used_space()

Return the amount of used space in the page.

[Validate]