Slide 14.6: An AVL tree (cont.) Slide 14.8: Multilevel indexing Home

A Paged Binary Tree

---

Each disk read produces a minimum of a single page—at least 512 bytes. Reading only a binary node wastes most of the data read from the disk. The paged binary tree attempts to address the problem by locating multiple binary nodes on the same disk page.

By dividing a binary tree into pages and then storing each page in a block of contiguous locations on disk, we should be able to reduce the number of seeks associated with any search.

The maximum number of seeks required for searching the paged binary tree is log_K+1(N+1), assuming

• N is the number of keys in the tree,
• K is the number of keys held in a single page,
• each page contains a completely balanced full tree, and
• the pages are organized as a completely balanced full tree.

For example, if a file is with 134217727 keys and one single page holds 511 keys, the worst-case search performance for the three file structures is

• Unpaged binary tree: log₂(N+1) = log₂(134217727+1) = 27 seeks.
• AVL tree: 1.44×log₂(N+2) = 1.44×log₂(134217727+2) = 39 seeks.
• Paged binary tree: log_K+1(N+1) = log₅₁₁₊₁(134217727+1) = 3 seeks.

^†Paged binary trees reduce the number of disk accesses, however there are a lot of difficulties in maintenance (insertions and deletions).