next up previous
Next: Updates on B-Trees Up: B-Tree Index Files Previous: Structure of a B-Tree

Queries on B tex2html_wrap_inline829 -Trees

  1. Suppose we want to find all records with a search key value of k.
  2. In processing a query, we traverse a path from the root to a leaf node. If there are K search key values in the file, this path is no longer than tex2html_wrap_inline961 .

    This means that the path is not long, even in large files. For a 4k byte disk block with a search-key size of 12 bytes and a disk pointer of 8 bytes, n is around 200. If n =100, a look-up of 1 million search-key values may take tex2html_wrap_inline969 nodes to be accessed. Since root is in usually in the buffer, so typically it takes only 3 or fewer disk reads.

Osmar Zaiane
Mon Jul 13 13:28:03 PDT 1998