Slide 14.1: B-tree evloution
Slide 14.3: A binary search tree (cont.)
Home

A Binary Search Tree

The definition of a binary search tree is
A binary tree where every node's left subtree has values less than the node's value, and every right subtree has values greater. A new node is added as a leaf.
Consider the following list of keys: 
   KF  FB  SD  CL  HN  PA  WS  AX  DE  FT  JD  NR  RF  TK  YJ
This list can be expressed as a binary search tree on the right.

The binary search tree allows us to print out all the keys in sorted order by an inorder tree walk, which prints the key of the root of a subtree between the values in its left subtree and those in its right subtree.

Search
To search for a key k, a procedure begins its search at the root and traces a path downward in the tree. For each node x it encounters, it compares the key k with key[x]. If the two keys are equal, the search terminates. If k is smaller than key[x], the search continues in the left subtree of x; if k is larger than key[x], the search continues in the right subtree.
Thus, the running time of the search is O(h), where h is the height of the tree. Therefore, a binary search is not fast enough for disk resident indexing.