Автор: Чен Хао, инженер по разработке iOS, отдел фронтенд-разработки
При ежедневной разработке база данных снижает порог для работы с данными.Пока мы пишем определенный SQL, мы можем добавлять, удалять, изменять и запрашивать данные. За упрощением часто скрываются преимущества оптимизации производительности, и то же самое верно для баз данных, Мы знаем, что если нет индекса, данные запроса будут сканироваться в полной таблице, а индекс подобен каталогу book, что значительно повышает эффективность запросов. В этой статье вы познакомитесь с индексом базы данных, поймете структуру данных индекса, а также познакомитесь с другими концепциями индекса.
структура данных индекса
Индексы в основном оптимизируют скорость поиска. Для заданных данных мы можем использовать последовательный поиск. Если данные уже отсортированы, мы можем использовать двоичный поиск. Если количество данных для поиска невелико, мы можем построить двоичный поиск поиск.Дерево помещает поиск в память, а структура данных индекса развивается из сбалансированного двоичного дерева.Прежде чем мы формально представим структуру данных индекса, давайте взглянем на двоичное дерево поиска.
бинарное дерево поиска
Двоичное дерево поиска требует, чтобы значение ключа левого поддерева всегда было меньше значения ключа корня, а значение ключа правого поддерева всегда было больше значения ключа корня.
Проблема с бинарными деревьями поиска заключается в том, что если одна ветвь слишком длинная, это сильно повлияет на эффективность поиска и даже приведет к последовательному поиску.
Чтобы повысить эффективность поиска бинарного дерева, бинарное дерево, которое необходимо построить, сбалансировано — сбалансированное бинарное дерево требует, чтобы разница высот двух поддеревьев любого узла была не более 1. Сбалансированное бинарное дерево обычно требует левого и правого вращения для достижения баланса.
Б* дерево
B-дерево
Давайте сначала посмотрим на описание B-дерева:
- B B-дерева представляет не бинарный, а сбалансированный
- B-дерево не является бинарным деревом, B-дерево является n-разветвленным (n > 2)
- Каждый узел имеет несколько ключевых слов, а между ключевыми словами есть указатели на дочерние узлы.
- Ключевые слова в узле расположены в порядке
- Все листовые узлы находятся на одном уровне
Для поиска поиск дерева B аналогичен двоичному дереву, поскольку ключевые слова в каждом узле отсортированы по ключу [1...n], мы можем использовать двоичный поиск для поиска ключевого слова k и ключ [i]. Сравните, чтобы найти поддерево соответствующего интервала.
Упрощенный код для поиска B-дерева:
Result BTreeSearch(BTNode *t, KeyType k) {
BTNode *p = t; *q = NULL; // q 指向 p 的双亲
int found = 0, i = 0;
while (p != NULL && found == 0) {
i = BinarySearch(p, k);
if (i > 0 && p->key[i] == k) {
found = 1;
} else {
q = p;
p = p->ptr[i];
}
}
...
}
Приведенный выше код также может использовать рекурсию. При таком базовом понимании нетрудно обнаружить, что эффективность поиска B-дерева связана с высотой дерева: чем меньше высота, тем меньше время поиска.
Далее рассмотрим вставку и удаление B-деревьев. Для вставки, если узел все еще имеет пустую позицию, вставьте ее напрямую, в противном случае узел будет разделен на две части, а ключевое слово в средней позиции будет вставлено в родительский узел.Если родительский узел не удовлетворен, Вставляйте до тех пор, пока процесс не достигнет корневого узла.
Вставка 15
Удаление немного сложнее вставки.Если после удаления ключевого слова количество ключевых слов в узле не меньше его коэффициента заполнения, удаляем его напрямую
удалить 8, 16
В противном случае возможны два случая:
- Если количество ключевых слов левого (правого) родственного узла больше, чем коэффициент загрузки, переместите максимальное или минимальное ключевое слово левого (правого) узла вверх к родительскому узлу, а затем переместите большее или меньшее ключевое слово в родительском узле. узел вверх перемещается вниз к узлу, который нужно удалить.
удалить 15
- Если количество ключевых слов левого (правого) родственного узла равно коэффициенту заполнения, то необходимо объединить узел, удаляющий ключевое слово, с ключевым словом левого (правого) узла и ключевым словом родительского узла, разделяющим два ключевых слова. в один Для узла, если количество ключевых слов родительского узла меньше, чем коэффициент заполнения, такая же обработка выполняется для родительского узла, так что высота всего дерева может быть уменьшена на один слой.
Результат после удаления 4
Из вышеизложенного видно, что вставка и удаление B-деревьев требуют больших затрат, поэтому нам также нужно очень внимательно относиться к установлению индексов базы данных, иначе необоснованные индексы снизят эффективность.
В+ дерево
Дерево B+ является разновидностью дерева B и часто используется в структуре индекса.Основные отличия между ним и деревом B:
- Все листовые узлы в дереве B+ содержат все ключевые слова, то есть ключевые слова нелистовых узлов также появляются в листовых узлах.
- Указатель конечного узла больше не указывает на индекс другого уровня, а прямо указывает на запись файла данных
- Узел ответвления не содержит адреса хранения, соответствующего ключевому слову, а содержит только указатели на каждый дочерний узел.
- Все листовые узлы связаны в линейный связанный список
Важным отличием дерева B от сбалансированного двоичного дерева является размер узлов и высота результирующего дерева Размер узла дерева B+ обычно равен размеру дискового блока, то есть размеру массива данных. страницы, поэтому дерево B короткое и толстое, а бинарное дерево высокое и тонкое. Как упоминалось ранее, эффективность поиска дерева B связана с его высотой.Предполагая, что данные в текущей таблице данных равны N, а количество элементов данных в каждом блоке диска равно m, тогда h = ㏒(m+1 )N, а m = размер блока диска / размер элемента данных, размер блока диска фиксирован, поэтому чем меньше размер элемента данных, тем меньше высота дерева. Вот почему индексные поля должны быть как можно меньше. Точно так же отказ от хранения данных в узлах ветвления означает сохранение как можно большего количества элементов данных.
Индекс дерева B+
Индекс дерева B+ — это реализация дерева B+ в базе данных. Одной из характеристик B+-индексов в базе данных является высокий уровень разветвления.Поэтому в базе данных высота B+-дерева обычно составляет от 2 до 4 слоев, что означает, что для нахождения индекса требуется не более 2-4 строк. записи строк с определенным значением ключа, умноженные на ввод-вывод.
Индекс дерева B+ не может найти конкретную строку для данного значения ключа. Все, что может найти индекс дерева B+, — это страница, на которой просматривается строка данных. Затем база данных считывает страницу в память, затем выполняет поиск в памяти и, наконец, получает данные для поиска.
Кластерные и вторичные индексы
Индекс дерева B+ можно разделить на кластерный индекс и вторичный индекс.Основное различие между ними заключается в том, что для кластерного индекса требуется уникальный ключ (обычно первичный ключ) для построения индекса и физический порядок хранения записей в файле. согласуется с порядком индекса. Фактические страницы данных могут быть отсортированы только в соответствии с деревом B+, поэтому каждая таблица может иметь только один кластеризованный индекс. Ключ вспомогательного индекса может не быть уникальным. Вспомогательный индекс может повысить производительность поиска ключей, отличных от кластеризованного индекса, что также увеличит определенные накладные расходы.
В следующей таблице есть три столбца, а именно идентификатор (первичный ключ), имя и зарплата.Давайте рассмотрим принципы кластерного индекса и вспомогательного индекса:
Выше приведен кластеризованный индекс
Выше приведен вспомогательный индекс
совместный индекс
Мы уже представили использование индексов для одного столбца. Совместный индекс относится к индексированию нескольких столбцов в таблице. Суть совместного индекса также является деревом B+. Давайте посмотрим на внутреннюю структуру объединенного индекса:
Для приведенного выше рисунка (1, 1), (1, 2), (2, 1), (2, 4), (3, 1), (3, 2) данные по (а, б) Порядок сохраняется, первый столбец сортируется в порядке возрастания, а второй столбец сортируется в соответствии с первым столбцом.
Поэтому для запросаSELECT*FROM TABLE WHERE a=xxx and b=xxx, очевидно, можно использовать совместный индекс (a, b). Для одного столбца запросSELECT*FROM TABLE WHERE a=xxx, вы также можете использовать этот индекс (a,b). но для запроса по столбцу bSELECT*FROM TABLE WHERE b=xxx, нельзя использовать индекс дерева B+. Можно обнаружить, что значение b на листовом узле равно 1, 2, 1, 4, 1, 2, что, очевидно, не отсортировано, поэтому запрос столбца b не может использовать индекс (a, b).
Совместный индекс может сортировать второе значение ключа после индексирования первого значения ключа. Например, запросите статус покупок пользователя, отсортируйте их по времени и, наконец, извлеките последние три записи о покупках.В настоящее время использование объединенного индекса может избежать еще одной операции сортировки, потому что после индексации идентификатора пользователя записи о покупках уже в порядке.
Как упоминалось ранее, совместный индекс (a, b) на самом деле сортируется по столбцам a и b, поэтому выражениеSELECT...FROM TABLE WHERE a=xxx ORDER BY bРезультат можно получить напрямую, используя индекс объединения.
Однако для совместного индекса (a, b, c) утверждениеSELECT...FROM TABLE WHERE a=xxx AND b=xxx ORDER BY cилиSELECT...FROM TABLE WHERE a=xxx ORDER BY bРезультат также можно получить непосредственно через совместный индекс.
но для заявленияSELECT...FROM TABLE WHERE a=xxx ORDER BY c, объединенный индекс не может получить результат напрямую, потому что c не использует индекс.
Это характеристика сопоставления крайнего левого префикса индекса. Согласно этому принципу, когда мы строим совместный индекс, мы должны учитывать, что запрос может максимально использовать индекс, что также требует от нас максимально возможного выбора столбца с высокой степенью дискриминации в качестве индекса.
резюме
- В столбце, который является первичным ключом, необходимо обеспечить уникальность столбца и расположение данных в организационной таблице.
- В столбцах, которые часто используются в соединениях, эти столбцы в основном представляют собой некоторые внешние ключи, которые могут ускорить соединение.
- Создайте индекс для столбца, в котором часто требуется выполнять поиск по диапазону, поскольку индекс уже отсортирован, а указанный диапазон является непрерывным.
- Создавайте индексы для столбцов, которые часто необходимо сортировать, поскольку индекс уже отсортирован, чтобы запросы могли использовать преимущества сортировки индекса, ускоряя время выполнения сортировки.
- Создайте индекс для столбца, который часто используется в предложении where, чтобы ускорить определение условия.
Хэш-индексы и битовые индексы
Наконец, краткое введение в две другие структуры индекса
хэш-индекс
Поиск хэш-индекса осуществляется с помощью хеш-алгоритма, и для разрешения конфликтов используется метод цепных адресов.Мы знаем, что временная сложность хеш-алгоритма составляет O (1), поэтому хэш-индекс очень эффективен.
Поскольку записи хеш-индекса не упорядочены каким-либо определенным образом, это также делает хэш-индекс непригодным для поиска по диапазонам.
Битовый индекс
Битовый индекс (bitmap index) — это специальный индекс, предназначенный для запроса нескольких столбцов, битовый индекс подходит для большого количества повторяющихся значений в столбце.
Структура таблицы:
| ID | gender | income_level |
|---|---|---|
| 43123 | m | L1 |
| 65654 | f | L2 |
| 76534 | f | L1 |
| 12343 | m | L4 |
| 65765 | f | L3 |
Растровое изображение пола:
| m | 10010 |
| f | 01101 |
Растровое изображение уровня_дохода:
| L1 | 10100 |
| L2 | 01000 |
| L3 | 00001 |
| L4 | 00010 |
| L5 | 00000 |
Приведенная выше таблица не дает никакого улучшения производительности для запросов, основанных только на поле. Однако для запросаSelect * from t where gender = 'f' and income_level = 'L3', индекс растрового изображения выполняет пересечение (логическое И) двух растровых изображений. То есть пересечение растрового изображения гендера = f(01101) и растрового изображения уровня дохода = L2(01000) дает растровое изображение 01000. Очевидно, что для запросов с большим количеством повторяющихся элементов данных в нескольких столбцах растровые индексы могут повысить эффективность поиска. Кроме того, растровые индексы имеют то преимущество, что они малы.
Суммировать
Эта статья является моими заметками по изучению индексации базы данных.Она только знакомит с принципами работы нескольких индексов баз данных, не углубляясь в исследования более низкого уровня.Она может играть лишь определенную роль в том, как устанавливать и выбирать индексы в повседневной разработке. Оптимизация производительности запросов по-прежнему требует обобщения опыта из большой практики.