# US 8,788,505 B2 · Systems and methods for a cache-sensitive index using partial keys > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,788,505 B2 - Document ID: US8788505B2 - Status: Granted - Kind: B2 - Application number: 13/094,942 - Filed: 2011-04-27 - Published: 2012-11-01 - Granted: 2014-07-22 - Earliest claimed: 2011-04-27 - Assignees: VeriSign, Inc. - Applicants: Michael Bentkofsky; Florent Guiliani - Inventors: Michael Bentkofsky; Florent Guiliani - Web page: https://patentgrep.com/patent/US8788505B2 ## CPC - G06F 16/285: {Clustering or classification} - G06F 16/214: {Database migration support} - G06F 16/2246: {Trees, e.g. B+trees} - G06F 16/2272: {Management thereof} - G06F 16/24552: {Database cache management} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract 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. ## Claims ### Claim 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, 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. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the node referenced by the child group pointer is identified based on an offset and the offset comprises a node size multiplied by a position of the current partial key within the current node. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein when the search value is greater than the key referenced by the full key pointer corresponding to the current partial key, the method further comprises performing the setting of the current partial key to the next partial key of the current node. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, wherein when the search value is less than the key referenced by the full key pointer corresponding to the current partial key, the method further comprises performing the setting of the current node to the node referenced by the child group pointer of the current node and the setting of the current partial key to the first partial key of the identified node. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein when the search value partial key is greater than the current partial key, the method further comprises recalculating the search value partial key. ### Claim 6 (depends on 5) The computer-implemented method of claim 5, wherein recalculating the search value partial key comprises: calculating a new byte offset by: adding two to the first byte offset when the first three bytes of the search value partial key match the first three bytes of the current partial key, and adding one to the first byte offset when the first two bytes of the search value partial key match the first two bytes of the current partial key; and adjusting the subset of the search value according to the new byte offset. ### Claim 7 (depends on 6) The computer-implemented method of claim 6, wherein when the new byte offset exceeds a predetermined value, the new byte offset comprises an additional byte and the subset of the search value comprises one less byte. ### Claim 8 (depends on 1) The computer-implemented method of claim 1 further comprising: determining that the search value is not located in the database based on the comparing the search value partial key to the current partial key; and outputting an indication that the search value is not located in the database in response to the determining. ### Claim 9 (depends on 1) A computer readable medium storing instructions for causing a processor to perform the computer-implemented method of claim 1. ### Claim 10 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. ### Claim 11 (depends on 10) The system of claim 10, wherein the child group pointer and the number of fixed size partial keys fit in a cache line of the cache line size. ### Claim 12 (depends on 10) The system of claim 10, wherein nodes of each group of nodes are stored contiguously in the cache memory. ### Claim 13 (depends on 12) The system of claim 12, wherein the node referenced by the child group pointer is identified based on an offset and the offset comprises a node size multiplied by a position of the current partial key within the current node. ### Claim 14 (depends on 10) The system of claim 10, wherein when the search value is greater than the key referenced by the full key pointer corresponding to the current partial key, the operations further comprise performing the setting of the current partial key to the next partial key of the current node. ### Claim 15 (depends on 10) The system of claim 10, wherein when the search value is less than the key referenced by the full key pointer corresponding to the current partial key, the operations further comprise performing the setting of the current node to the node referenced by the child group pointer of the current node and the setting of the current partial key to the first partial key of the identified node. ### Claim 16 (depends on 10) The system of claim 10, wherein when the search value partial key is greater than the current partial key, the operations further comprise recalculating the search value partial key. ### Claim 17 (depends on 16) The system of claim 16, wherein the operation of recalculating the search value partial key comprises: calculating a new byte offset by: adding two to the first byte offset when the first three bytes of the search value partial key match the first three bytes of the current partial key, and adding one to the first byte offset when the first two bytes of the search value partial key match the first two bytes of the current partial key; and adjusting the subset of the search value according to the new byte offset. ### Claim 18 (depends on 17) The system of claim 17, wherein when the new byte offset exceeds a predetermined value, the new byte offset comprises an additional byte and the subset of the search value comprises one less byte. ### Claim 19 (depends on 10) The system of claim 10, wherein each group of nodes of the groups of nodes comprises a number of nodes, the number of nodes being one more than the number of fixed size partial keys. ### Claim 20 (depends on 10) The system of claim 10, the operations further comprising: determining that the search value is not located in the database based on the comparing the search value partial key to the current partial key; and outputting an indication that the search value is not located in the database in response to the determining. ### Claim 21 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. ### Claim 22 (depends on 21) The non-transitory computer-readable storage medium of claim 21, wherein the node referenced by the child group pointer is identified based on an offset and the offset comprises a node size multiplied by a position of the current partial key within the current node. ### Claim 23 (depends on 21) The non-transitory computer-readable storage medium of claim 21, the method further comprising: determining that the search value is not located in the database based on the comparing the search value partial key to the current partial key; and outputting an indication that the search value is not located in the database in response to the determining. ### Claim 24 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.