Taming Trees: B-Trees

he previous article in this series on trees showed how to build a sorted binary tree. Inserting and locating items in a sorted tree is relatively quick and easy, so it's natural to wonder if you could use a sorted tree as an index for a database. To find a record, you could look up its key in the tree and then the node containing that key would contain a reference to the complete record's location. This method is simple and effective, but a normal sorted tree has some drawbacks that prevent it from behaving as you would expect.

This article discusses the reasons why ordinary sorted trees don't work well as indexes and explains B-trees (pronounced "bee trees"), the data structures that are actually used by databases to build index structures. It also offers a B-tree program (in both Visual Basic and C#) for download, but none of the code is included the article body because it's fairly involved.