发明名称 |
Data tree storage methods, systems and computer program products using page structure of flash memory |
摘要 |
A tree data structure is stored in a flash memory device by storing a leaf node and an index node comprising a pointer to the leaf node in a same page of the flash memory device, which may be read on a per-page basis. A modified version of the leaf node and a modified version of the index node may be stored in a new page of the flash memory device when, for example, a key value is added to or deleted from the leaf node. |
申请公布号 |
US9058253(B2) |
申请公布日期 |
2015.06.16 |
申请号 |
US200812167324 |
申请日期 |
2008.07.03 |
申请人 |
Samsung Electronics Co., Ltd. |
发明人 |
Kang Dong-Won;Kang Jeong-Uk;Kim Jin-Soo;Park Chan-Ik |
分类号 |
G06F17/30;G06F12/02 |
主分类号 |
G06F17/30 |
代理机构 |
Myers Bigel Sibley & Sajovec, P.A. |
代理人 |
Myers Bigel Sibley & Sajovec, P.A. |
主权项 |
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;
wherein the index node and the leaf node comprise a first index node and first leaf node of a first branch from a higher-level node shared with a second branch comprising a second index node and a second leaf node;wherein storing a leaf node and an index node comprising a pointer to the leaf node in a same page of the flash memory comprises storing the first leaf node and the first index node in a first page; andwherein the method further comprises: storing the higher-level node in the first page;storing the second leaf node and the second index node in a second page; 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. |
地址 |
KR |