Množina: btrees

A tree structure for storing database indexes. Each node in the tree contains a sorted list of key values and links that correspond to ranges of key values between the listed values. To find a specific data record given its key value, the program reads the first node, or root, from the disk and compares the desired key with the keys in the node to select a subrange of key values to search. It repeats the process with the node indicated by the corresponding link. At the lowest level, the links indicate the data records. The database system can thus rapidly skip down through the levels of the tree structure to find the simple index entries that contain the location of the desired records or rows. See the illustration.