Browse Prior Art Database

Data Base Index Structure

IP.com Disclosure Number: IPCOM000046919D
Original Publication Date: 1983-Aug-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 2 page(s) / 40K

Publishing Venue

IBM

Related People

Gorbatenko, GG: AUTHOR [+3]

Abstract

The five ringed data base structure in the figure includes three index levels 1, 2, and 3, a data level 4, and an overflow 5. Each level is made up of one or more logical sectors 6 (L sectors), logically linked so as to form a ring. The numbers 7 associated with each L sector can be thought of as a disk address. Because of the linking, logically adjacent sectors need not be physically contiguous. At the outset, there is a head pointer 8 and one item in the sample list, "ABLE" 9. Since each sector 6 holds only 30 items, the 31st item 10 ("DOG") must start a new sector (in this case sector 60). For each new sector issued, an entry 11 is placed in the index level 3 above. Eventually, the index level 3 will be full, and a new sector will be required with a corresponding entry 12 above it.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 74% of the total text.

Page 1 of 2

Data Base Index Structure

The five ringed data base structure in the figure includes three index levels 1, 2, and 3, a data level 4, and an overflow 5.

Each level is made up of one or more logical sectors 6 (L sectors), logically linked so as to form a ring. The numbers 7 associated with each L sector can be thought of as a disk address. Because of the linking, logically adjacent sectors need not be physically contiguous. At the outset, there is a head pointer 8 and one item in the sample list, "ABLE" 9. Since each sector 6 holds only 30 items, the 31st item 10 ("DOG") must start a new sector (in this case sector
60). For each new sector issued, an entry 11 is placed in the index level 3 above. Eventually, the index level 3 will be full, and a new sector will be required with a corresponding entry 12 above it. Continuing in this fashion results in the figure shown after 33,025 entries. Each index entry 13 has a set of two values: the number of indexable items subtended by that entry 14, and the L sector address of the next lower index corresponding to that entry 15. The data level has either the data value itself, such as 10, or a pointer 16 to a data overflow area 5 if the data item is too large to fit in the fixed space. As an illustrative example, assume that the 32nd item in the list is desired. The head pointer 8 directs the start with sector 9. The first item 17 says that the first 27,000 entries are subtended by sector 2. Sector 2 at location 17 shows that...