A B-tree is a
index data structure designed (like all tree data structures) for fast
lookup,
insert and
delete of data items whose key is known. The special thing about B-trees is that they are designed for really
huge indexes that are far too big to fit in main memory and therefore reside on
mass storage, read:
harddisks. Now, the big problem with harddisks is that they have a high
latency, so that each
seek costs you dearly (in terms of time required). On the other hand, there is virtually no difference in cost between fetching one byte or a whole
disk page of several hundred or thousand consecutive bytes.
The B-tree structure is optimized for this behaviour in that it has a very high branching degree (100 or more), making it very shallow. This means that you need very few seeks to go down the tree - even the hugest indexes fit into a four or five level tree, and the first two levels can usually be cached in main memory. On the downside, the individual tree nodes are quite large - they take up a whole disk page, but we already saw that that is OK. They are also more difficult to handle, but it's worth the gain.
So how does it work? Basically, in each tree node you have between n and n/2 entries (except for the root node, which can have less), and it has one more child nodes than entries. The entries form an ordered list, and you usually scan through it using binary search. Each child node fits into the "gap" between two entries and contains keys that are larger than the entry on one side but smaller than that on the other side. The child nodes on the "edges" contain keys that are larger (or smaller, respectively) than all entries in the node.
Of course, to be really usable, a tree structure must not degenerate. The B-tree, like the AVL tree is balanced. Remember that each node contains between n/2 and n entries, thus the tree can't degenerate. How is this guaranteed? Simple: if a node already has n entries and another one is added, it is split into two nodes, and its parent gets one more entry. Thus, the split can propagate up the tree up to the root node. When the root is split, the tree becomes one level deeper. If an entry is deleted from a node that already has only n/2 entries, one entry is transferred from its neighboring node or, if that node is also down to n/2 entries, the two nodes are merged into one.
As you see, the B-tree is just perfect for managing large databases on disk - so perfect, in fact, that all DBMSs make heavy (if not exclusive) use of it or one of its variants.