Prefix-based leaf node storage for database system

摘要

Operating a database system comprises: storing a database table comprising a plurality of rows, each row comprising a key value and one or more attributes; storing a primary index for the database table, the primary index comprising a plurality of leaf nodes, each leaf node comprising one or more key values and respective memory addresses, each memory address defining the storage location of the respective key value; creating a new leaf node comprising one or more key values and respective memory addresses; performing a memory allocation analysis based upon the lowest key value of the new leaf node to identify a non-full memory page storing a leaf node whose lowest key value is similar to the lowest key value of the new leaf node; and storing the new leaf node in the identified non-full memory page.

主权项

1. A method of operating a database system, comprising:
storing a database table in a memory, the database table comprising a plurality of rows, each of the rows comprising a key value and one or more attributes, the key value for each row being uniquely associated with the row; storing, in the memory, a primary index for the database table, the primary index comprising a plurality of leaf nodes, a root node, and at least one intermediate branching node connecting the leaf nodes with the root node, each of the leaf nodes storing one or more of the key values and, for each stored key value, a respective memory address defining a storage location where the row that is uniquely associated with the respective key value is stored in the memory, wherein the storing of each of the leaf nodes in the memory comprises:
storing the leaf node in a particular one of a plurality of memory pages of the memory, each of the memory pages having a size that corresponds to a secondary storage page size of storage pages used when performing a checkpoint of the database table to a checkpoint image stored on a secondary storage, the particular one determined using a prefix of a lowest of the one or more key values stored in the leaf node to provide a physical clustering that stores leaf nodes having similar prefixes in physically-near ones of the memory pages to thereby enable the leaf nodes to be usable for quickly retrieving rows of the database table from the checkpoint image upon a restore of the database table from the checkpoint image; and performing the checkpoint of the database table, comprising:
checkpointing the rows by copying the rows to first ones of the storage pages of the secondary storage;checkpointing the primary index by copying the memory pages storing the leaf nodes of the primary index to second ones of the storage pages of the secondary storage, while the root node and the intermediate branching nodes are not copied to any of the storage pages of the secondary storage; andwriting, to third ones of the storage pages of the secondary storage, a leaf node page index that allows the first ones of the storage pages to be retrieved out of order upon a restore of the database table from the checkpoint image to the memory such that a particular one of the rows can be quickly retrieved from the first ones of the storage pages and restored to the memory, wherein the leaf node page index stores, in a page header for each of the second ones of the storage pages, a lowest of the key values stored in any of the leaf nodes stored therein.