#27: Хэш таблицы: функции и схемы хэширования

[00:20] Здарова! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Вы слушаете подкаст, в котором разработчик современной базы данных изучает, как они работают, и делится знаниями со слушателями. В последнее время я очень много говорю про B-деревья — думаю, вы это заметили. Но в комнате стоит слон, и с ним нужно что-то делать. Сегодня поговорим про хэш-таблицы и поймём, почему они проиграли гонку за звание главной структуры данных для индексов в современных хранилищах. Поехали!

[01:00] Пожалуй, хэш-таблица — это самая популярная структура данных после массива. По крайней мере, вопрос про то, как устроена хэш-мапа, задают примерно на каждом первом собеседовании на Java-разработчика. Это интересная структура данных, и там есть над чем подумать, так что давайте разбираться по порядку. Хэш-таблица — это неупорядоченный ассоциативный массив, который мапит ключ на значение. Для нахождения нужной ячейки внутри массива используется хэш-функция: она принимает на вход ключ, а возвращает число, которое и определяет позицию внутри ассоциативного массива. Сложность поиска в хэш-таблице обычно O(1), но в худшем случае может быть O(n).

[01:40] Можно чуть-чуть по-другому представить хэш-таблицу, смотрите как. Вот у нас есть стандартный массив из 10 ячеек. Каждая ячейка хранит ссылку на объект, в котором лежит значение, а ключ в нашем случае — это индекс в массиве. То есть в каком-то смысле обычный массив — это тоже хэш-таблица, но она поддерживает только числовые ключи, а хэш-функция ничего не делает, просто возвращает то же самое число. Поиск по ключу 5 будет выглядеть примерно так: сначала мы считаем хэш от пятёрки — это пятёрка, затем идём в массив по индексу 5 и проверяем ячейку на null. Если она пустая, то значения по ключу 5 нет, а если ссылка не пустая, то мы возвращаем значение по этой ссылке. Минус этой структуры данных в том, что она поддерживает только числовые ключи.

[02:54] Но эта задача легко сводится к уже решённой. Осталось применить к результату хэш-функции остаток от деления. Индексы в массиве начинаются с нуля, и самый большой индекс равен размеру массива минус один. Остаток от деления хэша на длину массива и есть искомый индекс внутри этого массива. Например, у нас всё тот же массив из 10 элементов — представьте такую плашечку из 10 ячеек: самый маленький индекс — 0, самый большой — 9. Допустим, хэш-функция вернула 12. Делим 12 на 9 и берём остаток от деления — это 3. Идём по индексу 3 в массиве и проверяем значение. Так устроена статическая хэш-таблица.

[03:34] Это представление очень наивное и в реальной жизни не используется, ведь для корректной работы этой структуры должны соблюдаться следующие условия. Первое: мы знаем количество элементов, которые нужно хранить, ещё на стадии создания хэш-таблицы, потому что если элементов в какой-то момент станет больше, то случится переполнение. Второе: ключи всегда уникальны. И третье: хэш-функция идеальна — то есть для любой пары key1 и key2, где key1 и key2 не равны, результаты хэш-функции для них будут разными. Если первые два условия можно как-то обойти, то третье в принципе невыполнимо: пространство ключей может быть настолько огромным, что однозначно отобразить его на меньшее пространство хэшей очень и очень трудно — на практике невозможно.

[04:20] Кстати, ситуация, когда для двух разных ключей генерируется один и тот же хэш-код, называется коллизией. И с ними нам придётся работать постоянно, если мы хотим реализовать свою хэш-таблицу. Для этого нужно принять два больших дизайн-решения — два архитектурных решения, которые потом повлияют на то, как наша хэш-таблица будет выглядеть, как будет устроена и какой перформанс будет выдавать. Первое — какую хэш-функцию мы хотим использовать для хэширования ключей.

[04:54] Основная задача хэш-функции — замапить большое, потенциально бесконечное пространство ключей на маленький домен чисел, чтобы потом по этим числам применить целочисленную арифметику и понять, в каком месте лежит пара ключ-значение. В простом примере это тот же остаток от деления на длину ассоциативного массива, по которому мы уже находим пары ключ-значение. Это задача, которую хэш-функция в принципе решает. Но при её решении перед нами всегда встаёт trade-off.

[05:30] Trade-off выглядит так. Мы можем быть очень быстрыми и, например, всегда возвращать константу — единицу. Это самая плохая хэш-функция: она быстрая, но даёт максимальный collision rate. Вот вам и вторая сторона trade-off: на одной чаше — being fast, быть быстрым, на другой — collision rate, сколько коллизий мы производим. Самое быстрое — возвращать единицу — производит максимальное количество коллизий, это экстремальное положение trade-off. С другой стороны — минимальный collision rate, потенциально равный нулю: коллизий не происходит вообще никогда. Но такую хэш-функцию действительно сложно посчитать, это будет долго по времени выполнения. И вот нам нужно найти такой trade-off, который устроит нас по collision rate, но при этом будет достаточно быстрым. Такие требования к хэш-функции, и дальше мы немного рассмотрим, какие они бывают.

[06:15] Но перед этим — второе архитектурное решение, которое нужно принять, когда мы реализуем свою хэш-таблицу. Это схема хэширования: как в целом будет устроен алгоритм внутри, как мы будем по результату хэш-функции находить значения. Ведь способов больше одного, и все они существуют опять же из-за того самого trade-off. В программировании, и в базах данных особенно, у нас постоянно какие-то решения — это trade-off; золотой пули почти никогда нет. Когда мы выбираем, по какому ключу делать индекс и какая будет его реализация, это тоже в каком-то роде trade-off.

[06:52] В конкретном случае схемы хэширования trade-off такой. Мы можем аллоцировать очень много памяти — потенциально всю, что у нас есть, — под хэш-таблицу, и тогда делать минимальные действия во время get и put: просто потому, что место для нового ключа всегда есть, и мы всегда можем его туда положить, не раздувая таблицу. Либо мы будем потреблять мало места — вначале это небольшая табличка, которая потом разрастается всё больше и больше, как это делает, например, знакомое нам B+-дерево. Но тогда нам нужно делать дополнительные приседания во время put, а иногда и get или delete: все эти операции будут сопряжены с чем-то, что замедляет время чтения и записи. Вот такой trade-off у схемы хэширования. Но прежде чем перейти к ней, давайте вернёмся на шаг назад и посмотрим, какие бывают хэш-функции и какая хэш-функция у нас сейчас в ходу.

[07:53] Тема хэш-функций — это огромная тема для исследований. Если кому-то интересно в неё погрузиться, я думаю, вы без проблем это сделаете. Я не хочу сильно углубляться в неё в подкасте, потому что подкаст всё-таки обзорный, дающий верхнеуровневое понимание того, как устроены базы данных, а конкретные алгоритмы вы всегда можете найти. Я лишь назову несколько хэш-функций, которые упоминаются, когда речь идёт про эффективные хэш-функции в базах данных. Это, например, алгоритм MurmurHash, изобретённый в 2008 году, — хэш-функция, которая для плюс-минус всего работает более-менее нормально. Для хэш-функции многое может решать, например длина ключей: если длина ключей меньше 64 байтов, то Google CityHash (изобретён в 2011 году) будет быстрее и перформить лучше, чем MurmurHash, потому что он задизайнен так, что с ключами меньше 64 байтов работает быстрее.

[08:56] Но есть и более хорошие решения. Есть то, что называется state of the art, что используется почти всегда и везде, — это алгоритм xxHash и разные его модификации. Единственное, что про него говорят, — что он изобретён тем же человеком, который изобрёл алгоритм сжатия zstd. Короче, умный чувак. И ещё он от Facebook. А если посмотреть на бенчмарки, то xxHash действительно перформит сильно лучше — прям заметно, раза в 2–3 круче по скорости: throughput у него в 2–3 раза выше, чем у всех алгоритмов, которые мы обсуждали до этого. Поэтому он безусловный лидер.

[09:37] Говорят даже, что… Вот ChatGPT мне, например, написал, что скорость этого алгоритма приближается к скорости оперативной памяти и что всё, мы уперлись в железо. Я, честно, это утверждение не проверял, поэтому и говорю, что оно сгенерировано нейросеткой. Но в целом, вроде бы, может быть, оно и недалеко от истины. Если же попытаться разобраться, как эти алгоритмы устроены внутри, чтобы понять, почему один быстрее другого, — то это просто чернейшая магия. Сложный код, и почему только к 2012 году изобрели алгоритм, который реально хорошо перформит, совершенно непонятно. По сути, это комбинация бинарных преобразований — сдвигов, умножений, делений; все эти процессорные инструкции как-то сгруппированы в цикле, и происходит какая-то магическая рейс-комбинация, которая в итоге даёт и нормальное распределение, и нормальный collision rate, и окей-скорость. Если кому интересно — можете погрузиться, но для подкаста, мне кажется, достаточно понимать, что xxHash от Facebook и создателя zstd — это state of the art, который используется в большинстве хэш-таблиц. А мы идём дальше.

[11:01] Определившись с хэш-функцией, нам нужно теперь определиться со схемой хэширования: как будет выглядеть ассоциативный массив, будет ли всё лежать в бакетах или это будет статическая таблица. Давайте потихоньку разберёмся, как вообще может быть устроена хэш-таблица. Помимо всем известной хэш-мапы из Java — если вы хоть раз готовились к собеседованию по Java, то знаете, как она устроена, — это не единственная схема хэширования. Самая простая схема — это linear probe hashing, по сути линейное статическое хэширование. Выглядит оно так. Представьте ассоциативный массив, тот самый, что мы представляли вначале, — по сути, просто массив, в ячейках которого лежит пара «ключ и значение». Именно пара, а не просто значение, потому что иногда недостаточно получить по хэш-функции расположение нужного value — нужно ещё взять ключ и проверить, тот ли это ключ. Помимо функции hashCode, нам нужно заиспользовать ещё и equals, поэтому там лежит ключ-значение.

[12:11] Вот мы взяли от ключа хэш, поделили это значение на длину ассоциативного массива, получили локацию внутри массива, прошли по ней, увидели там ключ-значение и прочитали, если оно есть, или сказали, что нет, если его там нет. Положить туда тоже просто: вычисляем хэш, делим, кладём — но кладём в случае, если там пустое значение, то есть есть место. Но, как мы знаем, могут случаться коллизии. И дальнейшее обсуждение исходит из того, что хэш-функция у нас не xxHash, у которого коллизии редки, а такая, что коллизии частые. Просто для понимания этих проблем и их решения будем считать, что коллизии возникают часто. Вот мы положили какое-то значение по ключу a, а потом кладём по ключу b и попадаем в ту же ячейку ассоциативного массива, потому что остаток от деления хэш-кода на длину массива получился тот же самый. Вот вам банальная классическая коллизия.

[13:10] Как мы будем её решать? В подходе linear probe hashing мы просто переходим на следующую ячейку массива. Попали во вторую ячейку — вторая занята; переходим на третью, третья не занята — кладём туда. Если опять коллизия, из третьей выходим в четвёртую. И так по порядку, линейно, один за одним, пока в конце концов не найдём пустую ячейку и не положим в неё. Подход понятный и интуитивный, но обладает некоторыми проблемами. Например, при чтении мы попадём в самую верхнюю ячейку — вторую, — но считываем мы ключ E, который лежит где-то в конце и чтобы его найти, линейно нужно пробежаться через полмассива. Вот мы и делаем этот линейный скан. То есть бинарный поиск внутри нам недоступен — в отличие, например, от B-деревьев, где, попав в листовой узел с отсортированными ключами, можно сделать по ним бинарный поиск. Здесь никакого бинарного поиска нет: мы просто один за одним считываем ключи, пока не найдём (или не найдём) наш ключ E.

[14:18] Проблема вот в чём. Представьте, мы забили почти весь массив — полмассива, — и все ячейки забиты через коллизию: мы постоянно попадали в индекс 2, в индекс 2, в индекс 2, и после этого выстроилась целая полоса пар ключ-значение, у которых хэш-код попадает в двойку. Когда мы хотим что-то прочитать, то попадаем в двойку, проходим, находим нужный ключ и возвращаем его. Это ещё неплохо. Но допустим, мы решили удалить какой-то ключ посередине — какой-нибудь ключ C. Мы его удаляем, оставляем пустое пространство, и что происходит при чтении? Начинаем читать, опять попадаем в двойку — там лежит A; переходим на следующую, в тройку, — там пустота. Наш алгоритм чтения говорит: окей, дошли до пустой ячейки, там ничего нет, значит дальше сканить смысла нет — и возвращает, что такого ключа нет. А он на самом деле есть — мы просто сделали пропуск в этой последовательности ключей.

[15:14] Чтобы пропуска не было, при удалении мы должны вставлять специальный маркер удаления. Тогда при чтении, пройдя через этот маркер, мы поймём, что ячейка не пустая — там не null, а лежит указатель на объект «deleted item». Поняв, что здесь deleted item, мы пойдём считывать дальше, потому что цепочка чтения потенциально ещё не закончилась. А вот при вставке мы проверяем и на null, и на пустоту, и на deleted item: если при вставке попадаем в ячейку с deleted item, то просто берём и вставляем. Такой вот алгоритм linear probe hashing.

[15:53] Его основная проблема, особенно применительно к базам данных, в том, что мы делаем довольно много мутирующих операций. Мы мутируем наш массив, а мутация — это, как мы знаем, изменение состояния страницы: она становится грязной, и это всё потом должно как-то зафлашиться из кэша в долговечную память. В общем, для баз данных это довольно неэффективный подход. Есть несколько попыток улучшить эту схему хэширования — не меняя всё кардинально, а поправив логику добавления ключей, следующих друг за другом.

[16:27] Первая такая попытка называется Robin Hood hashing. Честно говоря, я не сильно понимаю, почему он работает и использует ли его кто-то, но суть в том, что Robin Hood начинает немного трекать collision rate внутри какой-то области памяти. Например, из-за коллизий у нас друг за другом выстроились пары ключ-значение в какую-то большую цепочку. При удалении и добавлении этот алгоритм понимает, что цепочка слишком длинная и её условно нужно сократить, сделать замещение. За счёт этого немного улучшается время поиска, потому что full-scan мы начинаем делать быстрее — длина всех этих сплошных последовательностей так или иначе уменьшается. Но, опять же, происходит это ценой ещё больших мутаций: мы ещё больше пишем, удаляем, перезаписываем, меняем эти ключи между собой. Robin Hood, кстати, называется так потому, что там есть дополнительный маркер, циферка — сколько последовательностей нужно пройти, чтобы вставить ключ. Этот ключ считается как бы бедным, а тот, что стоит на своём месте, — богатым; и бедный с богатым меняются местами. Таким образом название «Робин Гуд» оправдывается.

[17:39] Если мы много пишем в нашу хэш-таблицу и редко из неё читаем, то этот алгоритм, кажется, не сильно подходит. Поэтому есть ещё один алгоритм, придуманный, чтобы тоже не менять схему хэширования кардинально, а как-то её улучшить, — называется он cuckoo hashing. Ребята придумали использовать не одну статическую хэш-таблицу внутри (например, linear probe hashing), а две, три, четыре — N хэш-таблиц и, соответственно, N хэш-функций. Хэш-функции между собой различаются только сидом. Я не сказал, когда мы обсуждали хэш-функцию, что каждую хэш-функцию можно настроить таким значением, как сид. Если установить один и тот же сид, хэш-функция всегда будет возвращать одно и то же значение для одного и того же ключа — что мы и ожидаем, что логично. Но мы можем этот сид поменять, чтобы получить другое значение для того же ключа той же самой хэш-функцией.

[18:37] И хэш-таблица 1 использует внутри, например, сид один, а хэш-таблица 2 — сид два. Таким образом, если при put мы попадаем в первую хэш-таблицу и там уже есть такое значение, то делаем второе хэширование второй хэш-функцией и пытаемся вставить во вторую таблицу. Скорее всего, там коллизии не будет, потому что это уже другое значение. А когда у нас N хэш-таблиц, становится совсем хорошо: рано или поздно найдётся таблица, в которую мы попадём. По сути, коллизий как таковых на уровне одной хэш-таблицы нет, но есть коллизии на уровне многих таблиц. Поэтому, если при get мы читаем ключ E из хэш-таблицы 1, а получили ключ A, то мы такие: ага, в этой таблице лежит другой ключ, пойду в другую — идём в другую, читаем там. И в конце концов либо находим E, либо нет. Внутри таблиц тоже могут быть коллизии, потому что коллизий может быть много, а хэш-таблиц — недостаточно; они разруливаются уже на уровне каждой таблицы. Но суть в том, что их сильно меньше за счёт использования многих хэш-таблиц. Это алгоритм cuckoo hashing.

[19:46] До этого момента мы говорили про схемы хэширования для так называемых статических хэш-таблиц — по сути, это были статические схемы. Что значит статические? Что мы не разбирали алгоритмы увеличения хэш-таблицы: мы как бы подразумевали, что аллоцируем достаточно большие таблицы, чтобы их не увеличивать и переполнений не происходило. Но в жизни динамические хэш-таблицы часто оказываются лучшим выбором, потому что мы хотим экономить память: не хотим заранее аллоцировать огромные таблицы ради нормального перформанса, а хотим динамически разрастаться при необходимости, а вначале использовать мало памяти. И у нас есть ряд динамических схем хэширования — это chained hashing, extendable hashing и linear hashing.

[20:34] Chained hashing, я думаю, вы все так или иначе знаете или хоть раз с ним сталкивались — это стандартная схема хэширования в хэш-мапе в Java. По сути, chained hashing подразумевает наличие бакетов. То, как эти бакеты разрастаются, тоже влияет на нейминг: иногда это может быть не chained hashing, а что-то другое, и, возможно, в Java, кстати, не chained. Но суть в том, что для хранения пар ключ-значение мы используем не тот же ассоциативный массив, что раньше, а ссылку на бакет. То есть ассоциативный массив перестаёт хранить пары ключ-значение, а начинает хранить ссылку на бакет. А бакет — это, по сути, структура данных, которая может хранить в себе много пар ключ-значение. В целом он хранит какое-то фиксированное количество, а чтобы вырасти, мы делаем ссылку на следующий бакет — происходит как бы overflow.

[21:25] Представили: у нас есть ассоциативный массив, вначале небольшой, потому что хэш-таблица динамическая и может разрастаться. То есть вначале там плюс-минус адекватное количество слотов, и в значениях массива идут ссылочки на бакеты, которые для простоты являются обычными массивами фиксированного размера. Почему в базах данных фиксированный размер важен? Потому что, я думаю, вы уже знаете, как работают диски и как работает кэширование страниц в памяти: чем меньше мутаций мы делаем на структурах данных, тем лучше. Например, в Java для бакетов в старых версиях используется linked list, а с какого-то момента — древовидная структура данных, динамически увеличивающаяся, которая постоянно мутируется: чтобы добавить новый элемент, мы его просто туда добавляем и увеличиваем структуру. В Java это нормально, потому что хэш-мапа живёт в оперативной памяти, проблем нет. А вот с дисковой структурой данных, какие используются в базах данных для индексов, будут проблемы, потому что мы будем постоянно мутировать бакеты, а мы этого не хотим.

[22:33] Поэтому размер бакетов в подходе chained hashing фиксированный. И если бакет переполняется, мы делаем одну ссылку на overflow bucket — просто создаём новый, аллоцируем новую страницу и делаем ссылку на предыдущий. Таким образом мутировать мы будем всегда новую страницу, а старая, если мы вставляем много элементов, останется неизменной. Итак, chained hashing состоит из бакетов: мы в них кладём, а если бакет переполняется, создаём новый. При чтении по хэш-функции попадаем в нужный бакет и там ищем линейным поиском (или, если мы smart enough и держим ключи отсортированными, — бинарным, но в целом это будет линейный поиск внутри бакета или списка бакетов).

[23:18] Проблема этой классической структуры данных, chained hashing, в том, что непонятно, в какой момент мы насоздавали столько бакетов переполнения — их просто много, они выродились в огромный список, — что теперь наш маленький ассоциативный массив нужно удвоить, утроить или удесятерить в размере, чтобы бакетов было меньше и мы быстрее по ним пробегали, потому что рано или поздно мы в это упрёмся. А в базах данных, когда данных много, высокие throughput’ы, много чтения и записи, эту проблему — расплетование хэш-таблицы, слияние бакетов, её увеличение — решить не очень-то тривиально, потому что, пока мы всё это делаем, мы кого-то так или иначе будем блокировать.

[24:01] Поэтому есть второй подход к хэшированию — extendable hashing. Про него, я думаю, кто-то из вас слышал: подход довольно старый, изобретён то ли в 79-м году, если не ошибаюсь, и давно используется внутри баз данных, но, как правило, обычного программиста, когда он готовится к собеседованию, про extendable hashing точно никто не спросит, и, думаю, большинство собеседующих не смогут объяснить, как он работает. Но мы как раз для этого тут и собрались — слушаем подкаст, чтобы выйти за обычные рамки и познакомиться с новым алгоритмом. Честно, для меня, когда я ресёрчил и готовился, стало открытием, что такой подход к хэшированию существует и широко используется.

[24:46] Как он работает? Представим тот же ассоциативный массив со ссылочками на бакеты — он так и есть, но единственное его отличие в том, что ссылается он не совсем на бакет в прежнем смысле. В chained hashing мы говорим: пройдёшь по этой ссылке — получишь весь список ключей, у которых хэш-код равен вот этому; то есть у нас стопроцентное соответствие хэш-кода бакету, проходишь по бакету — там все ключи с хэш-кодом 5. В extendable hashing навигация немного другая. Хэш-код мы тоже берём, но представляем его сразу как биты — просто берём битовое представление хэш-кода. Допустим, мы хэшируем какую-то строку и получили 16 битов — у нас такая хэш-функция. И мы говорим: если переходишь по этому бакету — там все хэш-коды, у которых первый бит равен 0; по этому — где первый бит равен 1; по этому — где первые два бита равны 10; а тут — где первые два равны 11. Мы как бы переходим на бакеты, у которых первые (или последние — зависит от интерпретации) биты равны такому-то значению.

[26:09] Как понять, насколько битов смотреть? Даже в примере я сначала сказал «первый бит равен какому-то значению», потом «первые два, первые три» и так далее. Это определяется каунтером, который называется global counter и лежит рядом с ассоциативным массивом. Каунтер может быть равен, например, 2 — тогда внутри массива мы считываем первые два бита; если global counter равен 3 — считываем первые три бита и по ним навигируем по бакетам. Фишка в том, что у нас тоже может быть переполнение, и мы тоже навигируемся, но когда происходит переполнение, старые бакеты никак не изменяются — сплитится только тот бакет, который переполнился. И вместе со сплитом переполненного бакета мы увеличиваем global counter — была двойка, стала тройка, — и длина нашего ассоциативного массива умножается на 2.

[27:07] То есть вместо того, чтобы смотреть на первые два бита, мы теперь, раз где-то случилось переполнение, смотрим на три бита, и пространство поиска просто увеличилось. После того как мы переполним ещё где-нибудь, где уже три бита, мы такие: и этого не хватает — давай смотреть на четыре бита, и ещё раз в два раза увеличим ассоциативный массив. Таким образом мы сплитим только те бакеты, где произошло переполнение, а там, где не произошло, всё остаётся так же: как лежали эти страницы на диске, так и будут лежать. В этом основной прикол extendable hashing. Понимаю, что было немного сумбурно и непонятно; в целом это визуально довольно понятно — можно вбить в YouTube «extendable hashing», посмотреть видосик, и всё станет ясно.

[28:00] Ну и давайте, наверное, последнюю схему хэширования не то что рассмотрим и поймём, а узнаем, что она существует, — потому что реально объяснять схему хэширования в подкасте нужен прям талант, а я таким, наверное, не обладаю. Поэтому просто попытаюсь объяснить верхний уровень на пальцах. А если вам интересно и вы реально захотите понять и представить — либо Google, либо YouTube. Я оставлю ещё ссылочку на лекцию Энди Павло, которой вдохновлялся для этого конкретного выпуска. Если вдруг в подкасте непонятно — в лекции вы всё поймёте, там всё разжёвано, правда, идёт она почти полтора часа.

[28:37] Так вот, linear hashing, который для динамических таблиц, всё так же представляет бакеты, и они всё так же переполняются. Единственная его новация относительно chained hashing — то, как таблица разрастается. А разрастаться она будет так: помимо обычной работы хэш-таблицы (есть get и put, и мы идём-идём-идём) у нас есть ещё отдельный указатель — так называемый split pointer, указатель на сплитование. Он как бы говорит: вот я сейчас указываю на бакет, который буду сплитить, независимо от того, какой из других бакетов расширится. То есть если я указываю на первый бакет, а переполнение произошло во втором, я всё равно сделаю сплит первого бакета и потом перейду ко второму. Если я указываю на второй бакет и он заоверфлоился — сделаю сплит его, потому что указатель split pointer сейчас на нём, — и потом перейду к третьему. А если третий не переполнится, а переполнится, например, первый, — я не буду переходить к первому и его сплитить: останусь на третьем и сделаю сплит третьего. Это просто такой линейный, идущий сверху вниз указатель, который при переполнении какого-то бакета сплитит тот, на который указывает.

[30:00] Вообще, эта идея вначале кажется немного странной: если что-то у тебя переполнилось, то давай сделаем сплит того, что переполнилось, а не какого-то другого — а ты делаешь ровно наоборот тому, что нужно. Но вот интересный момент: если посмотреть на структуру данных не в конкретный момент добавления или удаления ключа, а статистически, под нагрузкой, — как она перформит, — то можно понять, что да, вот на промежутке в 10 секунд мы что-то не то сплитили, но если мы активно вставляем, то в те бакеты, которые сейчас засплитили, мы потом положим, и в тот момент нам уже не нужно будет делать сплит — он будет готов заранее. В этом основной прикол. Мысль в том, что рано или поздно мы и этот бакет расплитим, и тот расплитим, поэтому давайте уже сплитить тот, который готовы сплитить. Тем самым перформанс выравнивается под нормальной нагрузкой с нормальной хэш-функцией, и этот алгоритм реально работает. Если кому интересно — ссылка на лекцию будет в описании, там всё можно рассмотреть подробнее.

[31:06] Давайте вспомним, с чем мы сегодня познакомились. Это статические хэш-таблицы, хэш-функции и различные схемы хэширования — такие как linear probe hashing, cuckoo hashing, бакетирование и extendable hashing. Большинство этих техник используются внутри баз данных; самый яркий пример — hash join, его мы рассмотрим в следующих эпизодах. Но, несмотря на отличный перформанс на чтение, хэш-таблицы почти никогда не используются для реализации индексов — почти всегда это будет B+-дерево или что-то очень похожее. Почему так происходит?

[31:40] Смотрите. B+-дерево показывает примерно такой же перформанс даже при чтении по единственному ключу. Получается, что на практике эта структура данных не сильно уступает хэш-таблицам даже там, где хэш-таблицы сильны. И помимо этого B+-дерево поддерживает быстрое создание индекса на основе отсортированных данных, чтение по ключу и по диапазону ключей и эффективное отсортированное сканирование. Получается, что B+-дерево не просто так называют лучшей структурой данных для индекса. В следующих выпусках поговорим про LSM-деревья и разберёмся с ACID-транзакциями раз и навсегда. Не забывайте делиться подкастом с друзьями и коллегами — давайте прокачивать себя и людей вокруг. Ну а на этом всё. Услышимся!