Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Software Table Look-Up Buffer for B-Tree Implementation

IP.com Disclosure Number: IPCOM000040418D
Original Publication Date: 1987-Nov-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 2 page(s) / 45K

Publishing Venue

IBM

Related People

Udupa, DKR: AUTHOR [+2]

Abstract

In simple find operations on an indexed database, providing a Software Table Look-Up Buffer (TLB) reduces page faults. The search for an entry in the index starts first on the TLB. The TLB is resident in main memory after the first access. This eliminates the need for further page faults for entries found in the TLB. Basically, there are two cases of find operations. In one case, the decision involves whether an entry matching an argument is found or not. In the second case, it may be required to search the adjacent entry or entries based upon certain conditions. A TLB is be useful for the find operations which involve deciding whether an entry matching an argument is found or not. The total time during the search phase can be broken down to the time for paging operations and the time for searching nodes.

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 55% of the total text.

Page 1 of 2

Software Table Look-Up Buffer for B-Tree Implementation

In simple find operations on an indexed database, providing a Software Table Look-Up Buffer (TLB) reduces page faults. The search for an entry in the index starts first on the TLB. The TLB is resident in main memory after the first access. This eliminates the need for further page faults for entries found in the TLB. Basically, there are two cases of find operations. In one case, the decision involves whether an entry matching an argument is found or not. In the second case, it may be required to search the adjacent entry or entries based upon certain conditions. A TLB is be useful for the find operations which involve deciding whether an entry matching an argument is found or not. The total time during the search phase can be broken down to the time for paging operations and the time for searching nodes. (Each node of a B-tree has a set of entries.) The time for paging operations constitutes a major portion of the total search time. During find operations, a search is first made on the TLB (a software associate memory). If the TLB is not present in main memory, there will be a page fault. The TLB will be brought into main memory.

(Image Omitted)

If an entry is found in the TLB, it is retrieved. If the entry is not found in the TLB, the index is searched. If a matching entry is found in the index, that entry is brought into the TLB replacing the least used entry in the TLB. For subsequent searches in the TLB...