Databases Reference
In-Depth Information
TOCAB Storage Engine—
Implementing Indexes
In this chapter, we will implement the most complex plugin of the topic. Indexes are
crucial for the performance of the storage engine and a big part of Storage Engine
API deals with indexes, different types of indexes, various ways of using them, and
numerous index-related optimizations. We will inevitably have to cut corners to
keep the size of this chapter in bounds. Although the plugin that we will develop
here will be a fully working storage engine, it will be by no means feature complete.
At the end of the chapter, we will discuss what this engine is missing and what
features it could get to become a usable general purpose storage engine.
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 topic. 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
use, and reasonably portable. Unfortunately, it does not it 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.
