Имитация индекса базы данных

Индексы баз данных — это своего рода волшебство. Вы применяете индекс к определенному столбцу, и все запросы, использующие этот столбец, выполняются чудесным образом быстрее!

Вы когда-нибудь задумывались, как они реализованы?

В этой статье мы не будем погружаться в реальную внутреннюю структуру базы данных (хотя вам могут понравиться ссылки), но я надеюсь дать вам краткое представление о том, как можно имитировать работу базы данных.

Хотя для примеров кода использован Kotlin, он должен быть применим к большинству языков программирования без большой переделки.

Наивное хранилище

Давайте начнем с простого хранилища объектов:

data class User(val email: String)

object store {
    private val users = mutableListOf<User>()

    fun add(user: User) {
        users.add(user)
    }

    fun find(email: String): User? {
        for (user in users) {
            if (user.email == email) {
                return user
            }
        }
        return null
    }
}
Вход в полноэкранный режим Выход из полноэкранного режима

В нем будет храниться внутренний список пользователей, и, получив email, он будет перебирать список и возвращать нужного нам пользователя, либо нулевое значение, если он не найден:

fun main(args: Array<String>) {
    val user = User("john@doe")
    store.add(user)

    val found = store.find(user.email) ?: "not found"
    println("user is ${found}") // user is john@doe

    val notFound = store.find("not@found") ?: "not found"
    println("user is ${notFound}") // user is not found
}
Вход в полноэкранный режим Выход из полноэкранного режима

Измерение времени поиска пользователя

Чтобы сравнить затраченное время, давайте реализуем вспомогательную функцию:

fun timeTaken(fn: () -> Unit): Long {
    val before = Calendar.getInstance().timeInMillis
    fn()
    val after = Calendar.getInstance().timeInMillis
    return after - before
}
Вход в полноэкранный режим Выход из полноэкранного режима

Примечание: время, затраченное в миллисекундах, не является метрикой для измерения сложности времени, поскольку оно сильно зависит от аппаратного обеспечения и технологии. Для обсуждения временной сложности будет использоваться нотация Big O, но для наглядности проще вывести на экран время в миллисекундах, поэтому я использую ее только в качестве инструмента бенчмаркинга.

Для поиска пользователя с помощью текущей реализации требуется линейное время (O(n)):

fun main(args: Array<String>) {
    for (i in 0 until 30_000_000) {
        val user = User(email="someone@${i}")
        store.add(user)
    }

    val milliseconds = timeTaken {
        val notFound = store.find("not@found")?.email ?: "not found"
        println("user ${notFound}")
        // user not found
    }
    println("time taken = ${milliseconds}")
    // time taken = 363
}
Вход в полноэкранный режим Выход из полноэкранного режима

Итерация над 30.000.000 элементами — это не шутка! Теперь представьте себе таблицу базы данных с триллионами записей.

Использование алгоритма двоичного поиска

Применение алгоритма двоичного поиска к методу find улучшит его, уменьшив временную сложность до O(log n). Из 30.000.000 записей потребуется всего 7 итераций, пока запись не будет найдена, поскольку список сокращается вдвое на каждой итерации. Это довольно значительное улучшение!

Однако мы вставляем записи по порядку в хранилище, и мы не можем полагаться на то, что список записей всегда будет упорядочен. Это сделает недействительным использование двоичного поиска по списку, а изменение метода add для вставки элементов по порядку заставит его работать в линейном времени, а это не очень хорошая идея.

Но что, если вместо списка у нас была бы структура данных, в которую мы могли бы вставлять и искать элементы гораздо более эффективным способом?

Здесь приходит умная идея использовать для индексов самобалансирующееся двоичное дерево поиска.

Индекс как самобалансирующееся дерево двоичного поиска

Для того чтобы иметь эффективный индекс для поиска, нам нужна структура данных для хранения наших значений таким образом, чтобы мы могли эффективно применять двоичный поиск.

Дерево идеально подходит для этого, но если мы используем простое двоичное дерево и вставим элементы по порядку, дерево будет несбалансированным, потому что будут созданы только листья справа. Поэтому требованием является то, что это должно быть сбалансированное двоичное дерево.

Реализация сбалансированного двоичного дерева поиска — интересное упражнение, но в этой заметке оно рассматриваться не будет. В пакете java.util есть реализация под названием TreeMap, и мы воспользуемся ею. Под капотом это реализация красно-черного дерева, которое является своего рода самобалансирующимся двоичным деревом поиска, и оно гарантирует вставки, удаления и поиск за O(log n) в худшем случае.

Давайте погрузимся в него:

  1. Давайте добавим индекс для электронной почты пользователя в хранилище;
  2. Каждый раз, когда добавляется пользователь, мы вставляем его email в индекс вместе с позицией в списке;
  3. При поиске пользователя мы заменим линейный цикл for-loop на использование b-дерева, получая позицию для извлечения пользователя из списка;
import java.util.TreeMap

data class User(val email: String)

object store {
    private val users = mutableListOf<User>()
    private val emailIndex = TreeMap<String, Int>()

    fun add(user: User) {
        users.add(user)
        emailIndex.put(user.email, users.size-1)
    }

    fun find(email: String): User? {
        val idx = emailIndex.get(email) ?: -1
        return if (idx > -1) users.get(idx)
               else null
    }
}
Вход в полноэкранный режим Выход из полноэкранного режима

После повторного выполнения того же теста, теперь, когда у нас есть индекс, мы сможем увидеть, насколько велико влияние:

fun main(args: Array<String>) {
    for (i in 0 until 30_000_000) {
        val user = User(email="someone@${i}")
        store.add(user)
    }

    val milliseconds = timeTaken {
        val notFound = store.find("not@found")?.email ?: "not found"
        println("user ${notFound}")
        // user not found
    }
    println("time taken = ${milliseconds}")
    // time taken = 22
}
Вход в полноэкранный режим Выход из полноэкранного режима

Снижение с 363 до 22 миллисекунд!

Чем больше мы будем увеличивать количество записей, тем больше мы будем видеть расхождение во времени.

Почему не хэшмап?

Вы можете задаться вопросом, почему бы не использовать хэшмап?

Если мы хотим хранить все записи в памяти, то это хорошая идея. Это позволит нам избавиться от списка пользователей и дерева для индекса в пользу только хэшмапы, что приведет к постоянной вставке и просмотру (O(1)). Бинго!

Не так быстро, ковбой…

Если вы пытались следовать за нами, самостоятельно записывая код и запуская его, вы должны были столкнуться с ошибкой OutOfMemory. Ее можно легко решить, увеличив лимит памяти JVM с помощью параметра -Xmx4096m (где 4096m — объем памяти в МБ).

Таким образом, учитывая, что hashmap нужно загружать в память полностью, стоит ли использовать его, а не b-дерево?

Давайте поговорим о компромиссах

Как и почти все в программной инженерии, стоит ли использовать хэшмапу или b-дерево в качестве индекса, зависит от ситуации.

Наличие достаточного количества памяти для хранения всех данных делает хэшмэп гораздо более привлекательным, но если данные не помещаются в памяти, а хранить их на диске — это вариант, b-дерево можно хранить в файловой системе в виде небольших фрагментов, которые можно загружать по требованию.

Блоки, страницы и записи

В базах данных обычно существует абстракция страницы, расположенная поверх файловой системы, которая представляет собой структуру данных, содержащую набор записей. Сколько записей содержит страница, зависит от размера записей и размера блока в файловой системе.

Как правило, размер страниц примерно равен размеру блока файловой системы. Таким образом, данные хранятся в файловой системе в соответствии с размером блока, что позволяет избежать как можно большего количества пустых пробелов в блоке.

Вложенное b-дерево страниц и записей может быть использовано для загрузки данных по требованию, сохраняя при этом сложность O(log n). Как показано на упрощенной диаграмме ниже:

Заключение

Спасибо за чтение!

Мы рассмотрели много тем, и это уже довольно длинно. Давайте продолжим разговор о базах данных в следующих статьях.

Я надеюсь, что этот текст был дидактичным. Пожалуйста, оставляйте свои вопросы и комментарии и не забудьте проверить ссылки ниже. Если вы дошли до этого момента, то вам понравится читать их так же, как и мне.

Ссылки & Интересное чтение

  • SQLite Internals: Страницы и B-деревья
  • Индексные структуры B+Tree в InnoDB
  • То, что вы должны знать о базах данных

  • Изображение книжной полки с сайта Unsplash

Оцените статью
devanswers.ru
Добавить комментарий