Patent ID: 9058253
Filing Date: 2015-06-16
Classification: G06F

Abstract:
1. A method of storing a tree data structure in a flash memory device, the method comprising: storing a leaf node and an index node comprising a pointer to the leaf node in a same page of the flash memory device; storing a modified version of the leaf node and a modified version of the index node in a new page of the flash memory device, wherein the modified version of the leaf node comprises a new key value; dividing the leaf node into a first leaf node and a second leaf node if the leaf node is full; inserting a new key value in one of the first and second leaf nodes; detecting that removal of a key value from the first leaf node would result in no key values remaining in the first leaf node and that the first index node includes no other pointer to a leaf node; and responsively storing a modified version of the second index node in a third page.