Как реализовать простую реляционную базу данных?

Question

Обратите внимание, что этот вопрос касается только C++ . Меня не интересуют существующие библиотеки баз данных, и я не ищу универсального решения для «баз данных в C++». У меня есть конкретный вопрос, и я после самого эффективного (с точки зрения времени, пространства и лучшей практики) решения проблемы ниже.

Предположим, у меня есть серия книг, описанных Id, ISBN, Author и Name. Столбец Name будет идентификатором, который относится к отдельной таблице авторов, содержащей столбцы Id, Surname, First Name. Я хочу иметь возможность эффективно поиск по имени, а также по автору. Как я могу это структурировать и какие контейнеры использовать?

Эта тема была поднята несколько раз на SO и elsewhere, но никогда с ответом, относящимся конкретно к C++ или к реализации, не использующей существующие библиотеки.

Наивное решение было бы просто создать 2 отдельных классы: Author и 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; 
}; 

я мог бы создать векторы книги и автор (указатели). Но как бы я мог эффективно проиндексировать их? Предположим, я хочу найти книгу по ее ISBN; как я могу это сделать в постоянном или, по крайней мере, логарифмическом времени? Это возможно? Существует ли стандартная практика для такого рода проблем?

Answer 1

Прежде всего, стандартные контейнеры не поддерживают индексацию несколькими ключами - каждый контейнер поддерживает только один ключ. Это может быть составной ключ, поэтому, если у вас есть три книги с одинаковым названием разных авторов, вы можете указать как название, так и автора, чтобы найти только один из них. Однако ни один из стандартных контейнеров не поддерживает поиск по названию или автору.

Библиотека Boost Multi-Index поддерживает несколько ключей на элемент достаточно прямо. Учебник Multi-Index имеет example of creating foreign keys, так как вы заинтересованы в использовании.

Multi-Index поддерживает оба (красно-черные) древовидные и хэш-индексы. Как обычно, вы получаете компромисс между двумя хешированными индексами, как правило, дает быстрый поиск одного элемента, но индексы на основе дерева поддерживают неравенства, поэтому они обычно лучше, если вы хотите, например, поиск диапазонов (например, «книги авторов с фамилиями от« C »до« L »).

Answer 2

Стандартная структура данных для индекса является хеш-картой, если вам требуется только обратное сопоставление или двоичное дерево поиска, если вам также нужна сортировка. В C++ это unordered_map и map соответственно.

Предположим, я хочу найти книгу по ее ISBN;

unordered_map<std::string,Book*> и поиск будет постоянным.