SQL INDEX - как это работает?

Мои знания баз данных и SQL основаны в основном на университетских классах. Во всяком случае, я провел несколько месяцев (почти год) в компании, где я работал с базами данных.

Я прочитал несколько книг , и я принял участие в нескольких тренингах о базах данных , таких как MySQL, PostgreSQL, SQLite, Oracleа также несколько nonSQL dbлет такие компании MongoDB, Redis, и ElasticSearchт.д.

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

Позволь мне объяснить. Давайте возьмем базу данных SQL и создадим простую таблицу Personс несколькими записями внутри:

id | name   | age
-----------------
1  | Alex   | 24
2  | Brad   | 34
3  | Chris  | 29
4  | David  | 28
5  | Eric   | 18
6  | Fred   | 42
7  | Greg   | 65
8  | Hubert | 53
9  | Irvin  | 17
10 | John   | 19
11 | Karl   | 23

Теперь это та часть, на которой я хотел бы сосредоточиться - idэто INDEX.

До сих пор я думал, что это работает следующим образом: когда создается таблица, она INDEXпуста. Когда я добавляю новую запись в свою таблицу, INDEXона пересчитывается на основе некоторых алгоритмов. Например:

Группировка по одному:

1    ... N
N+1  ... 2N
     ...
XN+1 ... (X+1)N

Итак, для моего примера с size = 11 elementsи N = 3это будет так:

id | name   | age
-----------------
1  | Alex   | 24     // group0
2  | Brad   | 34     // group0
3  | Chris  | 29     // group0
4  | David  | 28     // group1
5  | Eric   | 18     // group1
6  | Fred   | 42     // group1
7  | Greg   | 65     // group2
8  | Hubert | 53     // group2
9  | Irvin  | 17     // group2
10 | John   | 19     // group3
11 | Karl   | 23     // group3

Итак, когда я использую запрос, SELECT * FROM Person WHERE id = 8он выполнит несколько простых вычислений 8 / 3 = 2, поэтому мы должны искать этот объект, group2а затем будет возвращена эта строка:

8  | Hubert | 53

Этот подход работает во время, O(k)где k << size. Конечно, алгоритм организации строк в группах, безусловно, намного сложнее, но я думаю, что этот простой пример показывает мою точку зрения.

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

Давайте еще раз возьмем эту таблицу:

id | name   | age
-----------------
1  | Alex   | 24
2  | Brad   | 34
3  | Chris  | 29
4  | David  | 28
5  | Eric   | 18
6  | Fred   | 42
7  | Greg   | 65
8  | Hubert | 53
9  | Irvin  | 17
10 | John   | 19
11 | Karl   | 23

Теперь мы создаем что-то похожее Hashmap(на самом деле, буквально это Hash Map), которое отображается idв addressстроке с этим идентификатором. Скажем так:

id | addr 
---------
1  | @0001
2  | @0010
3  | @0011
4  | @0100
5  | @0101
6  | @0110
7  | @0111
8  | @1000
9  | @1001
10 | @1010
11 | @1011

Итак, теперь, когда я запускаю свой запрос: SELECT * FROM Person WHERE id = 8

он будет сопоставлен непосредственно id = 8с адресом в памяти, и строка будет возвращена. Конечно сложность такая есть O(1).

Так что теперь у меня есть несколько вопросов.

1. Каковы преимущества и недостатки обоих решений?

2. Какой из них более популярен в современных реализациях баз данных? Может быть, разные БД используют разные подходы?

3. Существует ли он в не-DBS?

заранее спасибо

СРАВНЕНИЕ

               |      B-tree     |   Hash Table
----------------------------------------------------
----------------   one element   -------------------
----------------------------------------------------
SEARCHING      |  O(log(N))      | O(1) -> O(N)  
DELETING       |  O(log(N))      | O(1) -> O(N)
INSERTING      |  O(log(N))      | O(1) -> O(N)
SPACE          |  O(N)           | O(N)
----------------------------------------------------
----------------    k elements   -------------------
----------------------------------------------------
SEARCHING      |  k + O(log(N))  | k * O(1) -> k * O(N)
DELETING       |  k + O(log(N))  | k * O(1) -> k * O(N)
INSERTING      |  k + O(log(N))  | k * O(1) -> k * O(N)
SPACE          |  O(N)           | O(N)

N - количество записей

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

Вы в основном описываете индекс B-дерева и индекс хеша. У них обоих есть место, но оба лучше всего подходят для разных работ.

Преимущества и недостатки

Индексы B-дерева (и B + -дерева) обычно сбалансированы. Это означает, что поиск значения всегда будет занимать одинаковое количество времени, независимо от того, где в дереве оно падает (O (log n)). Как правило, количество уровней в дереве ограничено, поэтому оно имеет тенденцию становиться «шире», а не «глубже». Однако для небольших наборов данных стоимость обслуживания и использования B-дерева может быть больше, чем просто чтение всех строк. Индексы B-дерева хороши для больших наборов данных, наборов данных с низкой избирательностью или наборов данных, где вы намерены выбрать диапазон объектов, а не только один объект.

Хеш-таблицы отлично подходят для небольших наборов данных. Хеш-индексы имеют заранее определенное количество хеш-блоков в зависимости от используемого алгоритма хеширования. Это связано с тем, что данный алгоритм хеширования может производить только столько уникальных хэшей, поэтому он становится только «глубже», а не «шире». Как только механизм базы данных находит правильное ведро, он затем просматривает все объекты в этом ведре, чтобы найти тот, который вам нужен. С небольшими высокоселективными наборами данных каждая корзина содержит очень небольшое количество объектов и решается довольно быстро. С большими наборами данных ведра становятся намного более тесными. Таким образом, если нужный вам объект находится в небольшом ведре или находится в самом начале, он возвращается довольно быстро. Если это в конце большого ведра, это займет больше времени. Индекс не сбалансирован, поэтому производительность колеблется от O (1) до O (n).

популярность

В общем, я больше всего сталкивался с B-деревьями. Растровые индексы также являются еще одним вариантом для значений с низкой кардинальностью (например, логическое значение или, возможно, пол). Это будет варьироваться в зависимости от вашей базы данных, в зависимости от того, какие типы индексов доступны.

NoSQL

Базы данных NoSQL определенно поддерживают индексы. Большинство поддерживает B-дерево или вариацию B-дерева. Большинство, похоже, также поддерживают хешированные индексы.

Каковы преимущества и недостатки обоих решений? Второе решение не может выполнять сканирование диапазона. Это отлично подходит для выбора одного идентификатора. Но что, если вы хотите, чтобы идентификаторы с 3 по 8? Он должен захватывать все индивидуальные записи, которые в реальном мире - это не только O (1) * 6 записей для извлечения. В большой производственной базе данных с индексом HashMap вы будете получать записи на разных страницах, требуя, чтобы вы нажали на диск и прочитали шесть разных страниц в память.

В структуре B-Tree, например, как будет реализована ваша первая ситуация, идентификаторы будут последовательными на диске, и одна страница, скорее всего, будет содержать идентификаторы 3-8, увеличивая скорость сканирования диапазона, что сделает индивидуальный доступ O (log n) ,

Какой из них более популярен в современных реализациях баз данных? Может быть, разные БД используют разные подходы? У меня нет большого опыта в разных базах данных. Я знаю, что Sql Server в основном использует B-деревья, но в SQl 2014 есть несколько новых хеш-индексов, которые вы можете использовать для определенной таблицы. Я слышал, что многие базы данных No Sql и кэширующие базы данных, основанные на извлечении отдельных записей, также используют хеш-индексы. Это имеет смысл для кешей, так как вы хотите получить запись для пользователя A и не нуждаетесь в сканировании диапазона.

Существует ли он в не-DBS? Да. Бегло глядя на документацию создания индекса для postgressql, я вижу, что он поддерживает индексы Hash и B-Tree, а также некоторые другие.