How do I implement a simple relational database? [closed]

Question

Note that this question is about C++ only, I am not interested in using existing database libraries, nor am I seeking a generic solution to "databases in c++". I have a specific question and am after the most efficient (in terms time, space and best practice) solution to the problem below.

Suppose I have a series of books, described by Id, ISBN, Author, and Name. The Name column will be an ID which relates to a separate table of authors, containing the columns Id, Surname, First Name. I want to be able to efficiently search by Name as well as by Author. How would I go about structuring this, and what containers would I use?

This topic has been broached several times on SO and elsewhere, but never with an answer relating specifically to C++ or to an implementation not using existing libraries.

The naive solution would be simply to create 2 separate classes: Author and Book:

class Book
{
public:
  int id;
  std::string isbn;
  Author* author;
  std::string name;
};

class Author
{
public:
  int id;
  std::string surname;
  std::string givenName;
};

I could then create vectors of Book and Author (pointers). But how would I efficiently index these? Suppose I want to find a book by its ISBN; how can I do that in constant or at least logarithmic time? Is this possible? Is there standard practice for this kind of problem?

Answer 1

First of all, the standard containers don't support indexing by multiple keys -- each container supports only a single key. That can be a composite key, so if you have three books with the same title by different authors, you can specify both the title and author to find only one of those. None of the standard containers, however, supports searching separately by title or author.

The Boost Multi-Index library supports multiple keys per item fairly directly. The Multi-Index tutorial has example of creating foreign keys much like you're interested in using.

Multi-Index supports both (red-black) tree-based and hash-based indices. As usual, you get a trade-off between the two -- hashed indices usually give faster lookup of a single item, but tree-based indices support inequalities, so they're generally better if you want things like searching for ranges (e.g., "books by authors with surnames from 'C' to 'L'").

Answer 2

The standard data structure for an index are hash map if you only need reverse mapping or a binary search tree if you also need sorting. In C++, these are unordered_map and map respectively.

Suppose I want to find a book by its ISBN;

Create unordered_map<std::string,Book*> and searching will be constant time.