Insert optimization for B+ tree data structure scalability
A method, in one embodiment, can include receiving a key and associated data via a computing device. Furthermore, the method can include searching a B+ tree data structure using the key to find a leaf node. The B+ tree data structure is stored by a persistent storage coupled to the computing device. The B+ tree data structure can include a first plurality of nodes that each contains a key-value entry that is not maintained in a sorted order based on its key. In addition, the key and associated data are appended to the leaf node. A sector that includes the leaf node and the key and associated data can be flushed to the persistent storage.
1. A method comprising:
receiving a key and associated data via a computing device;
searching a B+ tree data structure using the key to find a target leaf node, wherein the B+ tree data structure is stored by a persistent storage coupled to the computing device, wherein the B+ tree data structure comprises a plurality of leaf nodes, wherein each leaf node of the plurality of leaf nodes is not maintained in a sorted order based on its key, and wherein each leaf node corresponds to a size of a sector of the persistent storage;
appending the key and associated data to the target leaf node in an atomic operation;
flushing the target leaf node to a target sector of the persistent storage in an atomic operation; and
flushing a first free space management structure associated with the B+ tree data structure to the persistent storage intermittently, wherein the first free space management structure indicates a first number of free blocks.
2. The method of claim 1 , further comprising:
detecting the sector size of the persistent storage; and
ensuring that each leaf node of the plurality of leaf nodes of the B+ tree data structure is not larger than the sector size of the persistent storage.
3. The method of claim 1 , wherein the flushing comprises reducing a second number of free blocks of a second free space management structure on the persistent storage, wherein the reduced second number of free blocks is not greater than the first number of free blocks.
4. A non-transitory computer readable storage medium having stored thereon, computer-executable instructions that when executed by a computing device cause the computing device to perform a method comprising:
receiving a key and associated data via the computing device;
searching a B+ tree data structure using the key to find a target leaf node, wherein the B+ tree data structure is stored by a persistent storage coupled to the computing device, wherein the B+ tree data structure comprises a plurality of leaf nodes, wherein each leaf node of the plurality leaf nodes is not maintained in a sorted order based on its key, and wherein each leaf node corresponds to a size of a sector of the persistent storage;
appending the key and associated data to the target leaf node in an atomic operation;
flushing the target leaf node to a target sector of the persistent storage in an atomic operation; and
flushing a first free space management structure associated with the B+ tree data structure to the persistent storage intermittently, wherein the first free space management structure indicates a first number of free blocks.
5. The non-transitory computer readable storage medium of claim 4 , wherein the B+ tree data structure further comprises a plurality of non-leaf nodes, wherein each non-leaf node of the plurality of non-leaf nodes is maintained in a sorted order based on its key.
6. The non-transitory computer readable storage medium of claim 4 , wherein the method performed by the computing device further comprises:
detecting the sector size of the persistent storage; and
ensuring that each leaf node of the plurality of leaf nodes of the B+ tree data structure is not larger than the sector size of the persistent storage.
7. The non-transitory computer readable storage medium of claim 4 , wherein the flushing comprises reducing a second number of free blocks of a second free space management structure on the persistent storage, wherein the reduced second number of free blocks is not greater than the first number of free blocks.
8. A computer system comprising:
a processor; and
computer readable storage media coupled to the processor and having stored therein instructions that, if executed by the computer system cause the computer system to execute a method comprising:
receiving a key and associated data via a computing device;
searching a B+ tree data structure using the key to find a target leaf node, wherein the B+ tree data structure is stored by a persistent storage coupled to the computing device, wherein the B+ tree data structure comprises a plurality of leaf nodes, wherein each leaf node of the plurality leaf nodes is not maintained in a sorted order based on its key, and wherein each leaf node corresponds to a size of a sector of the persistent storage;
appending the key and associated data to the target leaf node in an atomic operation;
flushing the target leaf node to a target sector of the persistent storage in an atomic operation; and
flushing a first free space management structure associated with the B+ tree data structure to the persistent storage intermittently, wherein the first free space management structure indicates a first number of free blocks.