INTRODUCTION

In class we discussed "Search Trees"--i.e. trees that have the "search property" (all the nodes to the left of a node have lower key values; all the nodes to the right of a node have a greater key value). However, we focused on binary trees, which work incredibly well if the tree is relatively small.

Some trees, on the other hand, are incredibly large. This necessitates storing the tree on disk and only paging in those parts which are currently being examined. Doing that means that our primary objective (to achieve efficiency) will be in reducing the number of disk hits.

B-Trees are a technique for doing that.