Browse Prior Art Database

Digital B-Trees

IP.com Disclosure Number: IPCOM000049478D
Original Publication Date: 1982-Jun-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 4 page(s) / 19K

Publishing Venue

IBM

Related People

Chandra, AK: AUTHOR [+2]

Abstract

A new tree index organization for files, capable of efficiently supporting both random and sequential access, is introduced. The organization, called digital B-tree (DB-tree), is similar in many aspects to B-trees. Its advantage is that it permits much larger fan-out per node, thus reducing the height of the tree for a given file size. The effect of this is to reduce the cost of a random access to the file. The fan-out of DB-tree nodes is increased substantially by permitting multiple page nodes. The unique advantage of DB-trees is that only one page of the node need ever be examined for each data access. This is accomplished by using the bits of the key to compute which page of the node is desired. Building DB-trees

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 29% of the total text.

Page 1 of 4

Digital B-Trees

A new tree index organization for files, capable of efficiently supporting both random and sequential access, is introduced. The organization, called digital B- tree (DB-tree), is similar in many aspects to B-trees. Its advantage is that it permits much larger fan-out per node, thus reducing the height of the tree for a given file size. The effect of this is to reduce the cost of a random access to the file. The fan-out of DB-tree nodes is increased substantially by permitting multiple page nodes. The unique advantage of DB-trees is that only one page of the node need ever be examined for each data access. This is accomplished by using the bits of the key to compute which page of the node is desired. Building DB-trees

Digital Btrees are called "digital" because of the manner in which the index entries are spread out among the nodes of the tree. Like B-trees, DB-trees grow as the file grows by a process of node splitting. The The way in which the splitting is performed is different, however.
1. A node does not always split when it becomes over-filled.

Rather, it may increase in size, i.e., become a

multi-page node.
2. When splitting an "over-filled" node. the entries are not

divided so as to yield an equal number of entries in each

resulting node. Instead, the division is on the basis of the

bit configuration of the key, i.e., in which half of the key

space each entry is contained. This "digital" splitting

is the reason for calling the index organization by the

name "digital B-tree".

All entries of a node of a DB-tree share some maximum length common prefix, and all index entries with that common prefix are contained in the node.

The posting of information in the next higher level (ancestor) node concerning the splitting of a node requires that we replace the entry associated with index term "x" with two new index terms, "x" Il '0'B and "x" Il '1'B. The index terms are not keys of the file but act as separators that direct a search down to the correct leaf. These terms are, in fact, the shortest possible separators for the splitting of a given node. The penalty in this form of splitting is that storage utilization is reduced. Doubling Node Size

Consider now a one page node that becomes over-filled. Instead of splitting the node into two nodes, we can replace the one-page node with a two-page node, distributing the entries across the two pages.

The entries are divided between the two pages of the two-page node exactly as if the node were being split into two nodes. Thus, into the first page go all entries with prefix 'x' II '0'B, while into the second page go entries with prefix 'x' rl '1'B'. Instead of replacing entry 'x' in the higher level index with two new entries, however, we instead update information associated with entry 'x' to indicate that this entry now references a two-page node. During a search, we need never access both pages. Entries beginning with 'x' Il 'O'B will access the first (Oth)

1

Page 2 of 4...