B-tree library

There are many different data structures that can be used as "indexes". Most popular are those of the B-tree family and hash tables. However, discussing details of different B-tree or hash table implementations is beyond the scope of this book. For our purposes, we will simply take an existing B-tree implementation. There are many libraries providing that or another implementation of some of the B-tree variant. We will build a MySQL storage engine on top of the LGPL licensed Tokyo Cabinet library (http://1978th.net/tokyocabinet/) by Mikio Hirabayashi. It is fast, simple to use, and reasonably portable. Unfortunately, it does not fit exactly into the MySQL Storage Engine API model-indeed, probably no third-party library does it out of the box-we will need to work around their differences. But first, let's see what the Tokyo Cabinet API looks like.

The library provides different types of storage. It can do hash tables (in memory and on disk), B+ trees (a variant of B-trees), and other, more specialized types. In our engine we will only use the B+tree API of Tokyo Cabinet, although an advanced storage engine could have used them all, selecting the most appropriate storage automatically, depending on the table structure.