Systems and methods for a cache-sensitive index using partial keys

摘要

Systems and methods are disclosed for a cache-sensitive index that uses fixed-size partial keys. The index may include a node comprising a child group pointer, a number of partial keys and a similar number of full-key pointers. The node may also include a record count. The nodes are organized into groups. The groups may contain a number of nodes one greater than the number of partial keys in a node and the nodes in a group may be stored contiguously in memory. The child group pointer and the number of partial keys may fit within a cache line. A method is disclosed for traversing the index, for bulk-loading the index, and for live deletion of records from the index.

主权项

1. A computer-implemented method of loading records into a search tree, comprising:
generating a sorted list of groups, by: reading a record from a database; populating a first full key, wherein a pointer to the first full key is in a first node of a group and the pointer to the first full key points to the record; pushing the group onto a stack; popping a top two stack entries in the stack based on a determination that a number of records in the top two stack entries is a power of two; combining the top two stack entries into a sorted list; pushing the sorted list onto the stack; based on a determination that the number of records in the top two stack entries is not a power of two, reading a current record from the database and populating a current full key, wherein a pointer to the current full key is a first node of a current group and the pointer to the current full key points to the current record; pushing the current group onto the stack; and based on a determination that there are no additional records to read in the database, combining all stack entries in the stack to generate the sorted list of groups, wherein: each group of the sorted list of groups comprises at least one node; and each node of the sorted list of groups comprises at least one pointer to a full key; generating a search tree, wherein the sorted list of groups corresponds to leaf nodes of the search tree; generating a root node and non-leaf nodes of the search tree; and generating partial keys for each full key with a pointer in the leaf nodes, each full key with a pointer in the non-leaf nodes, and each full key with a pointer in the root node of the search tree, wherein each partial key is a fixed size and comprises: a byte offset indicating a position the partial key differs from the corresponding full key; and a subset of the corresponding full key.