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

A system for locating a search value in a database, comprising:

• a cache memory having a cache line size and storing an index comprising groups of nodes, wherein each node of the groups of nodes 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;
• a processor;
• and
• a memory storing instructions that, when executed by the processor, cause the processor to perform operations 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, and
• determining 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.

A non-transitory computer-readable storage medium for locating a search value in a database, comprising:

• a cache memory having a cache line size and storing an index comprising groups of nodes, wherein each node of the groups of nodes 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;
• and
• instructions which, when executed on a processor, perform a 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, and
• determining 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.

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, and
• 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,
• determining that the search value is not located in the database based on the comparing;
• and
• outputting an indication that the search value is not located in the database in response to the determining.