В последнее время возникла необходимость модифицировать существующую структуру хранения, что предполагает рассмотрение условий запросов и эффективности запросов.После прочтения нескольких статей, связанных с индексами и HBase, я вспомнил соответствующие знания в сочетании с требованиями проекта и рассказал о своем собственное понимание и обобщение.
Часть контента взята из статей нескольких блоггеров, и, наконец, будет дана ссылка на статью, чтобы поблагодарить их за прекрасный анализ.
Он будет представлен со следующих аспектов:
- Зачем нужен индекс
- индексированная категория
- Эволюция индекса MySQL
- Оптимизация индекса MySQL
- Введение в HBase
- Структура хранилища HBase
- Введение в индексы HBase
- Бизнес-требования и дизайн
Я буду разделен на статьи 3. Эта статья в основном знакомит с первыми 3 разделами и понимает индекс MySQL, о котором мы часто говорим. Вторая статья посвящена методам анализа индекса и общей оптимизации индекса. Третья статья знакомит с HBase, используемым в бизнесе.
Зачем нужен индекс
Вообще говоря, индекс предназначен для повышения скорости запросов, когда объем данных относительно велик, недопустим поиск последовательно от начала до конца. Кроме того, сохраненные данные будут содержать несколько атрибутов для описания бизнес-объектов, атрибуты могут храниться непрерывно или отдельно, в соответствии с MySQL и HBase соответственно.
Если взять MySQL в качестве примера, сущность студента имеет такие атрибуты, как номер студента, имя, пол и класс, и обычно имеет идентификатор первичного ключа.Теперь есть требование: запросить имя студента, чей номер студента равен 002.
Данные хранятся на диске. Наименьшая единица, которую операционная система считывает с диска, — это блок. Если нет индекса, все данные будут загружены в память и последовательно извлечены. Всего загруженных данных будет много, и дисковый ввод-вывод будет больше.
При наличии индекса будет создан индекс с идентификатором учащегося в качестве ключа. MySQL использует древовидную структуру B+ для хранения. С одной стороны, загруженные данные содержат только идентификатор учащегося и идентификатор первичного ключа. Быстро, данные соответствующей строки можно быстро найти в соответствии с соответствующим идентификатором, поэтому скорость поиска будет очень высокой, поскольку общий объем загружаемых данных очень мал, а дисковый ввод-вывод невелик.
Видно, что индекс может сильно уменьшить диапазон извлекаемых данных, уменьшить дисковый ввод-вывод и сделать запрос быстрым, потому что дисковый ввод-вывод очень медленный, что определяется его аппаратной структурой.
Далее подробные подробные структуры и данные, хранящиеся в процессе определения положения диска, более глубокое понимание индекса.
Структура хранения жесткого диска
Внутренняя структура диска следующая:
- На веретено нанизано множество тарелок, и веретено быстро вращается вместе с ними;
- Каждая пластина имеет множество дорожек, и каждая дорожка разбита на сектора один за другим;
- Треки в одном и том же месте на нескольких пластинах образуют цилиндр;
- Каждая пластина имеет магнитную головку, которая может считывать и записывать данные;
При обращении к данным можно сказать: вынуть данные 1 цилиндра, 1 магнитной головки и 1 сектора?
Диск переместит 1 головку на 1 цилиндр, что является соответствующей дорожкой, которая называется «время поиска», а затем повернет диск, пусть головка укажет на 1 сектор, и начнет чтение данных, что называется «время вращения». , и скорость высокая.Жесткий диск может быстрее вращаться до определенного сектора, поэтому производительность будет лучше.
Структура более сложная, но операционная система инкапсулирует ее и предоставляет метод, называемый логическим блоком.Вы можете видеть, что диск состоит из «блоков» с номерами 1, 2, 3, ..n, а указанный блок — Convert его в цилиндр, головку, сектор, искать, вращать и считывать данные в соответствии с методом, упомянутым выше.
Чтобы облегчить нашу работу, операционная система дополнительно абстрагируется в файл.Файловая система сохраняет и читает данные.Нам нужно иметь дело только с файлом.Файл использует структуру inode, через которую все файлы, используемые файлом можно легко найти блок диска.
Сектор — это жесткий диск, блок — файловая система, а блок — наименьшая единица доступа к файлу.Как правило, блок состоит из нескольких последовательных секторов.
Блоки данных таблицы объединяются вместе в связанный список, и данные хранятся в блоках диска построчно в единицах строки.
процесс размещения данных
Возьмем в качестве примера дерево MySQL B+, кратко описываем процесс позиционирования данных в нескольких распространенных сценариях.
Первый сценарий: точный поиск по индексу
select * from user_info where id = 23 ;
Определите условия позиционирования, найдите номер страницы корневого узла, прочитайте корневой узел в память, выполните поиск вниз слой за слоем, прочитайте страницу листового узла и найдите запись или пропустите с помощью двоичного поиска.
Второй сценарий: поиск диапазона индекса
select * from user_info where id >= 18 and id < 22 ;
Считайте корневой узел в память, определите условие позиционирования индекса с идентификатором = 18, найдите первый конечный узел, который удовлетворяет условию, и просмотрите все результаты последовательно, пока условие завершения не удовлетворит идентификатор > = 22.
Третий сценарий: полное сканирование таблицы
select * from user_info where name = 'abc' ;
Непосредственно читать головной узел листового узла, последовательно сканировать, возвращать подходящие записи и заканчивать на последнем узле.
Четвертая сцена: поиск вторичного индекса
create table table_x(int id primary key, varchar(64) name , key sec_index(name) ) ;
select * from table_x where name = 'd' ;
Возьмите основной ключ по вторичному индексу, возьмите первичный ключ, чтобы проверить индекс основного ключа, вторичный индекс может отфильтровать много недопустимых записей, повысить эффективность
индексированная категория
Преимущества индексации и процесса позиционирования данных описаны выше, и у нас есть общее представление об этом.Кроме того, существуют разные типы и разные реализации индексов.В этом разделе основное внимание уделяется разбору этих понятий.
Кластеризованные и некластеризованные индексы
Проще говоря, кластеризованный индекс — это форма организации индекса.Логический порядок ключевых значений индекса определяет физический порядок хранения строк данных таблицы, тогда как некластеризованный индекс — это обычный индекс, который просто создает соответствующий индекс для столбца данных.Влияет на физический порядок хранения всей таблицы.
Преимущества кластерных индексов:
- Запрос диапазона более эффективен;
- Это особенно подходит для сценариев, где небольшая часть горячих данных часто читается и написана;
- Быстрая доступность при доступе к данным по первичному ключу;
Механизм InnoDB представляет собой кластеризованную индексно-организованную таблицу, и его правила выбора кластеризованного индекса следующие:
- Сначала выберите явно определенный индекс первичного ключа в качестве кластеризованного индекса;
- Если нет, выберите первый уникальный индекс, который не допускает NULL;
- Если нет, используйте встроенный ROWID механизма InnoDB в качестве кластеризованного индекса;
Индекс первичного ключа и вторичный индекс
Индекс первичного ключа, называемый первичным ключом, состоит из одного или нескольких столбцов и используется для уникальной идентификации записи в таблице данных.
Дизайн первичных ключей таблиц данных InnoDB обычно следует нескольким принципам:
- Используйте в качестве первичного ключа столбец атрибутов с автоинкрементом, не предназначенный для бизнеса;
- Значение поля первичного ключа всегда не обновляется, есть только две операции добавления или удаления;
- Не выбирайте тип, который будет обновляться динамически, например, текущая метка времени и т. д.;
Вспомогательные индексы, обычно называемые индексами, также называются вторичными индексами и далее делятся на уникальные индексы и неуникальные индексы.
В механизме InnoDB индекс первичного ключа будет выбран в качестве кластеризованного индекса, и нет существенной разницы в хранении между уникальным индексом и обычным вспомогательным индексом, за исключением ограничения уникальности.
Эволюция индекса MySQL
В этом разделе в основном рассказывается, как индекс шаг за шагом превращается в древовидную структуру B+ в соответствии с требованиями.Основная идея состоит в том, чтобы уменьшить общий объем данных, к которым осуществляется доступ, и, соответственно, уменьшить дисковый ввод-вывод.
Плотный индекс
По принципу уменьшения доступа к недопустимым данным мы берем значение ключа и сохраняем его в отдельном блоке. И добавьте к каждому значению ключа указатель, указывающий на исходный блок данных.
Сканирование таблицы больше не выполняется при выполнении операций позиционирования. Вместо этого выполните сканирование индекса (Index Scan), прочитайте все блоки индекса по очереди и выполните сопоставление ключ-значение.Проблема, связанная с этим, заключается в том, что для хранения плотного индекса требуется много места. Кроме того, эффективность позиционирования индекса относительно низка, а доступ к IO может быть уменьшен с помощью алгоритмов сортировки и поиска.
Если предположить, что в блоке можно хранить 100 строк данных, то для хранения 10 000 000 строк данных потребуется 100 000 блоков дискового пространства. Предположим, что столбец ключ-значение (+ указатель) занимает 1/10 пространства строки данных. Тогда для хранения индекса Dense необходимо около 10 000 блоков. Таким образом, мы обмениваем около 1/10 дополнительного пространства хранения примерно на 10-кратную эффективность позиционирования при полном сканировании таблицы.
Найти пополам
Dense нужно индексировать, и каждый индексный блок упорядочен, кроме того, требуется массив для хранения адресов индексных блоков по порядку, чтобы все было упорядочено, а массив также хранится на диске и размещается в отдельном цепочка блоков...
Временная сложность половинного поиска составляет O(log2(N)), и в приведенном выше примере плотный индекс содержит в общей сложности 10 000 блоков. Предполагая, что 1 блок может хранить 2000 указателей, для хранения этого массива необходимо 5 блоков. При поиске по полублоку нам нужно прочитать не более 5 (блоков массива) + 14 (блоков индекса log 2 (10000)) + 1 (блоков данных) = 20 блоков.
Как видно из рисунка, нумерация упорядочена относительно плотного индекса.
Разреженный индекс
При введении блочного поиска пополам мы обнаружили, что после чтения каждого блока ему нужно только сопоставить значение ключа первой строки, чтобы определить положение (направление) следующего блока. Следовательно, действительные данные — это данные первой строки каждого блока, а данные первой строки каждого блока вынимаются отдельно и складываются вместе с адресом индексного массива. Таким образом, вы можете напрямую выполнить половинный поиск в этом массиве, и этот массив превратился в разреженный индекс.
Блоки 10 необходимы для хранения адресов и значений ключей первой строки блоков плотного индекса 10,000.Благодаря индексации разреженного требуется только 10 (блоки разреженного) + 1 (блоки плотного) + 1 (блоки данных) = 12 блоков. .
Многослойный разреженный индекс
Поскольку сам разреженный индекс упорядочен, можно перестроить разреженный индекс для разреженного индекса. С помощью этого метода разреженные индексы строятся слой за слоем, пока самый верхний разреженный индекс не займет только один блок.
В этом примере разреженный индекс имеет только 10 блоков, и необходимо установить еще только один разреженный индекс.При поиске по двум слоям разреженного индекса и одному слою плотного индекса требуется только 1+1+1+1=4 блока. быть прочитанным.
Если сами данные сортируются на основе определенного ключа, то разреженный индекс может быть установлен непосредственно по данным без установления слоя плотного индекса (данные можно рассматривать как слой плотного индекса), который называется кластеризованным индексом.
В+ дерево
Поскольку значения ключей упорядочены, возможен поиск по диапазону. Необходимо только связать блок данных и блок Dense Index в виде двусвязного списка, чтобы добиться эффективного поиска по диапазонам. Как показано ниже:
Это то, что мы часто называем деревом B+, посмотрите вверх ногами:
Наконец, подытожим его характеристики:
- Каждый раз, когда выполняется операция позиционирования, поиск начинается с корня;
- Для каждого уровня индекса необходимо прочитать только один блок;
- Нижний плотный индекс или данные называются листьями;
- Каждый поиск должен искать конечный узел, чтобы найти данные;
- Количество уровней индекса называется высотой индексного дерева;
- Производительность операций ввода-вывода индекса тесно связана с высотой дерева индексов: чем выше дерево индексов, тем больше дисковых операций ввода-вывода;
- При выполнении поиска по диапазону это очень эффективно;
Справочная статья:
- Принцип индекса дерева Mysql-B +
- я жесткий диск
- Серия часто задаваемых вопросов | Кластерный индекс индекса MySQL
- От простого к глубокому пониманию реализации индекса
Добро пожаловать, чтобы отсканировать QR-код ниже, обратите внимание на мою личную общедоступную учетную запись WeChat и просмотрите другие статьи ~