The B-tree was invented in 1972 by R. Bayer and E. McCreight, and was designed from the start to create shallow trees for fast disk access. Shallow trees have few �levels�, We have to seek through them fewer times, and therefore they run quickly. Because seeks often require going to disk for the information we need, The performance increase with a shallow tree rather than a deeper tree can be substantial. B-trees are a powerful solution to the problem of disk-based storage; virtually every commercial database system has used variations on a B-tree for years. A B-tree consists of pages. Each page has a set of indices. Each index consists of a key value and a pointer. The pointer in an index can point either to another page or to the data you are storing in the tree. Thus, every page has indices that point to other pages or to data. If the index points to another page, the page is called a node page; If the index points to data, the page is called a leaf page.