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 locating a search value in a database, the database having an index comprising groups of nodes, wherein each node comprises: a child group pointer, a number of fixed size partial keys, and a number of full key pointers corresponding to the number of fixed size partial keys, the method comprising:
computing a search value partial key for the search value, wherein the search value partial key is a fixed size and comprises a first byte offset and a subset of the search value; setting a current node to a root node and setting a current partial key to a first partial key of the root node, wherein the first partial key of the root node is the fixed size and comprises the first byte offset and a subset of a key referenced by a first full key pointer of the root node; and comparing the search value partial key to the current partial key, wherein the comparing comprises;
when the search value partial key is less than the current partial key, setting the current node to a node referenced by a child group pointer of the current node and setting the current partial key to a first partial key of the identified node, wherein the first partial key of the identified node comprises a second byte offset and a subset of a key referenced by a first full key pointer of the identified node,when the search value partial key is greater than the current partial key, setting the current partial key to a next partial key of the current node, wherein the next partial key of the current node is the fixed size and comprises a third byte offset and a subset of a key referenced by a next full key pointer of the current node,when the search value partial key is equal to the current partial key, comparing the search value with a key referenced by a full key pointer corresponding to the current partial key, anddetermining that the search value matches the key referenced by the full key pointer; and outputting a record value corresponding to the key referenced by the full key pointer in response to the determining.