Separation of Common Text in B-Tree Entries
Original Publication Date: 1987-Jul-01
Included in the Prior Art Database: 2005-Feb-01
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.