Chapter 10. TOCAB Storage Engine — Implementing Indexes

In this chapter, we will implement the most complex plugin of the book. 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 book. For our purposes, we will simply take...