Browse Prior Art Database

Separation of Common Text in B-Tree Entries

IP.com Disclosure Number: IPCOM000039635D
Original Publication Date: 1987-Jul-01
Included in the Prior Art Database: 2005-Feb-01

Publishing Venue

IBM

Related People

Authors:
Brown, LG Pinnow, KW Udupa, DKR [+details]

Abstract

Portions of text that are common to individual entries in each node of a B-tree index are identified. This reduces the time needed to find an entry in the index. In addition, the removal of common text from individual entries in nodes of the index results in significant storage savings. Operations on an index are usually broken up into finds, inserts and deletes. Sometimes, insert and delete operations are lumped together as update operations. In any index operation, a part of, or the complete argument, becomes the search key depending upon the type of index operation. In each node, the length of common text of all the entries in the node is stored. For a search, the common text can be obtained from the first entry in a node and the length of common text. Common text lengths may have to be updated after inserts or deletes.