News Column

Patent Issued for Indexing Method for Flash Memory

August 20, 2014



By a News Reporter-Staff News Editor at Electronics Newsweekly -- A patent by the inventors Lee, Jaesoo (Gyeonggi-do, KR); Ahn, Jung-Sang (Daejeon, KR); Kim, Jin-Soo (Seoul, KR); Jung, Dawoon (Gyeonggi-do, KR), filed on October 14, 2011, was published online on August 5, 2014, according to news reporting originating from Alexandria, Virginia, by VerticalNews correspondents.

Patent number 8799558 is assigned to Samsung Electronics Co., Ltd. (KR).

The following quote was obtained by the news editors from the background information supplied by the inventors: "The present disclosure herein relates to a flash memory, and, more particularly, to an indexing scheme for a flash memory.

"Flash memory devices are non-volatile memory devices that do not require power to retain information stored in the memory chip. In addition, although not as fast as dynamic random access memory (DRAM) devices that are used as the main memories for personal computers, flash memory devices offer generally fast read speeds and better shock resistance than hard disks. Due to these characteristics, flash memories are widely used as storage devices in battery-operated devices. Another feature of flash memories is their virtual indestructibility against physical elements such as extreme pressure and boiling water.

"Flash memory devices are non-volatile computer memory devices capable of electrically erasing and rewriting data. Unlike electrically erasable programmable read-only memories (EEPROM), flash memory devices are capable of erasing and writing in block units. Because flash memory devices cost less than EEPROMs, they are generally used wherever a significant amount of non-volatile, solid state storage is needed. Representative applications include digital audio players, digital cameras, and mobile phones. Flash memory devices are also used in USB drives that are widely used for general data storage and transfer of data between computers.

"Increasing the speed of hard disks is structurally difficult because they mechanically drive magnetic disks to read/write data. Ongoing efforts have recently begun to use flash memories instead of hard disks as large capacity storage devices. In particular, when a boot code is stored in a flash memory device, the booting speed of the system becomes faster."

In addition to the background information obtained for this patent, VerticalNews journalists also obtained the inventors' summary information for this patent: "The present disclosure provides an indexing method for a flash memory, which leads to enhancement in performance and durability.

"Embodiments of the inventive concept provide an indexing method based on a tree structure of a flash memory including a plurality of pages, including: receiving a correction command for a leaf node and storing an entry in the leaf node and an entry in an index node designating the leaf node in the same page. The tree structure includes the leaf node and the index node, and the storing of the entry changes the maximum number of entries that are stored in the leaf node of the page and the maximum number of entries that are stored in the index node of the page on the basis of the number of entries in the leaf node and the number of entries in the index node, respectively.

"In some embodiments, the flash memory may be read and/or written in page units.

"In other embodiments, the index node may designate at least one leaf node.

"In still other embodiments, when a plurality of index nodes are included in the page, a top node among the index nodes may be a root node.

"In even other embodiments, when the correction command is a command indicating inserting of a new entry into the leaf node, the storing of an entry may further include: determining whether the leaf node is full; dividing the leaf node into first and second leaf nodes when the leaf node is full; and inserting the new entry into one of the divided first and second leaf nodes.

"In yet other embodiments, the storing of an entry may further include: determining whether the index node is full when the leaf node is divided into the first and second leaf nodes; determining whether the leaf node has a free space for storing the new entry when the index node is full; and changing the maximum number of entries which are stored in the leaf node of the page and the maximum number of entries which are stored in the index node of the page at a predetermined change ratio when the leaf node has the free space.

"In further embodiments, the storing of an entry may further include: dividing the index node when the index node is full and the leaf node has no free space for storing the new entry; and counting the number of divisions of the index node.

"In still further embodiments, the storing of an entry may further include: counting the number of divisions of the index node when the leaf node is divided; determining whether a ratio of the number of divisions of the index node and the number of divisions of the leaf node is greater than a predetermined value; determining whether the leaf node has the free space for storing the new entry when the ratio of the number of divisions of the index node and the number of divisions of the leaf node is not greater than the predetermined value; and changing the maximum number of entries that are stored in the leaf node of the page and the maximum number of entries that are stored in the index node of the page to increase the maximum number of entries that are stored in the index node when the leaf node has the free space.

"In even further embodiments, the determining of the ratio of the number of divisions may include determining whether (the number of divisions of the index node)/(the number of divisions of the leaf node) is greater than (1-a size ratio of the leaf node)/(a size ratio of the leaf node).

"In yet further embodiments, when the correction command is a command indicating deleting of an entry from the leaf node, the storing of an entry may further include: determining whether the leaf node becomes empty due to the deletion of the entry; deleting the leaf node when the leaf node becomes empty; determining whether a use ratio of the root node is less than a reference value; and changing the maximum number of entries that are stored in the leaf node of the page and the maximum number of entries that are stored in the index node of the page to increase the maximum number of entries that are stored in the leaf node when the use ratio of the root node is less than the reference value.

"In yet further embodiments, the determining of a use ratio may include determining whether the number of entries stored in the root node is less than 50% of the maximum number of entries stored in the root node.

"In much further embodiments, a size ratio the leaf node occupies in the page may be equal to or less than a first value and be equal to or greater than a second value, and the storing of an entry may include changing the maximum number of entries that are stored in the leaf node of the page and the maximum number of entries that are stored in the root node of the page to change the maximum number of entries that are stored in the leaf node in the range from the first value to the second value.

"In still much further embodiments, each of the plurality of pages may store the maximum number n (n is a positive integer) of entries of the leaf node and the maximum number n (n is a positive integer) of entries of the index node.

"In other embodiments of the inventive concept, a system includes: a flash memory including a plurality of pages; and a processor accessing the flash memory, wherein the processor performs the indexing method.

"In still other embodiments of the inventive concept, a system includes: a solid state disk (SSD) including a plurality of pages; and a processor accessing the SSD, wherein the processor stores data of a leaf node and data of an index node designating the leaf node, in the same page."

URL and more information on this patent, see: Lee, Jaesoo; Ahn, Jung-Sang; Kim, Jin-Soo; Jung, Dawoon. Indexing Method for Flash Memory. U.S. Patent Number 8799558, filed October 14, 2011, and published online on August 5, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8799558.PN.&OS=PN/8799558RS=PN/8799558

Keywords for this news article include: Samsung Electronics Co. Ltd.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Electronics Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters