Эта статья взята изРаспределенная инфраструктура в простых условиях - Статьи базы данных https://url.wx-coder.cn/kl3ms.

индекс базы данных

Индекс (Index) — это структура данных, которая помогает системе базы данных эффективно получать данные.Индекс базы данных — это, по сути, структура данных, используемая для повышения эффективности поиска данных в базе данных за счет добавления дополнительных операций записи и пространства для хранения для поддержания структура данных индекса. Индексы могут помочь нам быстро находить данные, не просматривая каждую строку в базе данных при каждом поиске. Типичный индекс, такой как сохранение двоичного дерева поиска в памяти, каждый узел содержит значение ключа индекса и указатель на физический адрес соответствующей записи данных, так что двоичный поиск может быть использован для его получения со сложностью O(log2n) для соответствующие данные.

Левая часть — это физический адрес записи данных, а правая — дерево поиска.Следует отметить, что логически соседние записи не обязательно являются физически соседними на диске. В реальных приложениях баз данных мы часто используем дерево B+ или LSM для замены двоичного дерева поиска или красно-черного дерева для построения системы индексов и полного ее использования.Управление виртуальным хранилищем https://url.wx-coder.cn/PeNqSПринцип локальности, концепции упреждающего чтения диска и кэша страниц, представленные в этом разделе.

Стоит отметить, что в этом разделе не рассматриваются технологии, связанные с индексацией текста, обычно используемые в поисковых системах, такие как инвертированный индекс, TF-IDF и т. д. Если вам интересно, вы можете обратиться к этой статье.Поисковик https://url.wx-coder.cn/O07eIГлава.

Основы управления хранилищем

Этот раздел взят изОбъясните операционную систему Linux простыми словами https://url.wx-coder.cn/Q0AmI.

Компьютерные запоминающие устройства можно условно разделить на две категории: основная память и внешняя память.Скорость доступа к памяти высокая, но емкость маленькая, дорогая и не может хранить данные в течение длительного времени.Исчезнет;скорость доступа к внешней памяти относительно медленный, но он может потреблять постоянное хранилище. На более детальном уровне устройства хранения данных в каждой компьютерной системе организованы в виде иерархии памяти, в которой устройства сверху вниз становятся все медленнее и медленнее в доступе, а их емкость увеличивается Большой размер, а стоимость байта становится все дешевле и дешевле .

Основная идея иерархии памяти заключается в том, что память одного уровня действует как кеш для памяти нижнего уровня. Таким образом, регистровый файл — это кеш для L1, который является кешем для L2, который является кешем для L3, который является кешем для основной памяти, который, в свою очередь, является кешем для диска. В некоторых сетевых системах с распределенными файловыми системами локальный диск представляет собой кэш данных, хранящихся на дисках в других системах.

основная память

Основная память — это временное запоминающее устройство, используемое для хранения программ и данных, обрабатываемых программой, пока процессор выполняет программу. Физически основная память состоит из набора микросхем динамической оперативной памяти (DRAM). Логически память представляет собой линейный массив байтов, каждый байт имеет свой уникальный адрес (т. е. индекс массива), и эти адреса отсчитываются от нуля. Как правило, каждая машинная инструкция, из которой состоит программа, состоит из разного количества байтов.

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

Когда системе необходимо прочитать основную память, адресный сигнал на адресную шину будет загружен в основную память, адресный сигнал считывания основной памяти и расположен в определенном блоке хранения аналитических сигналов, этом блоке хранения и данных на шина данных, для чтения других частей. Аналогичная процедура для записи в основную память, системный блок для записи в адрес и данные размещаются на адресной шине и шине данных, основная память для чтения содержимого двух шин, операция записи соответственно. Здесь видно, что время доступа к основной памяти линейно зависит только от количества обращений, поскольку механическая операция не существует, не имеет никакого эффекта «расстояние» двух обращений к данным в зависимости от времени, например, A0, затем возьмите вытесняющий A1 и А0 то бери Д3 первый бери расход времени такой же.

Регистры и кэши

Регистровый файл находится на самом верху иерархии, то есть на уровне 0 или L0. Типичный регистровый файл хранит всего несколько сотен байтов информации, в то время как основная память может содержать миллиарды байтов. Однако процессор может считывать данные из регистрового файла почти в 100 раз быстрее, чем из основной памяти. В ответ на эту разницу между процессором и основной памятью разработчики систем используют меньшее и более быстрое запоминающее устройство, кэш-память (называемую кэшем), в качестве временной области наращивания для хранения последней возможной памяти процессора. быть обязательным.

Кэши L1 и L2 реализованы с использованием аппаратной технологии, называемой статической оперативной памятью (SRAM). Более новые, более мощные системы имеют даже три уровня кэш-памяти: L1, L2 и L3. Система может получить большой объем памяти, а скорость доступа также высокая, потому что используется принцип локальности кэша, то есть программа имеет тенденцию обращаться к данным и коду в локальной области. Большинство операций с памятью можно выполнять в быстром кеше, если в кеше хранятся данные, к которым, вероятно, будут часто обращаться.

диск

Диск — это устройство хранения данных с прямым доступом (DASD). Он характеризуется небольшим изменением времени доступа. К любой группе символов можно получить прямой доступ, емкость большая, а скорость выше, чем у других внешних устройств хранения. Диск представляет собой плоский диск (похожий на пластинку на проигрывателе) с рядом кругов, называемых дорожками, на которые записываются данные. Диск может быть цельным или представлять собой группу дисков, состоящую из нескольких пластин, причем каждая пластина имеет две стороны. Возьмите в качестве примера набор из 6 дисков, как показано на рисунке ниже, за исключением того, что внешние стороны вверху и внизу не хранят данные, всего 10 сторон могут использоваться для хранения информации.

Когда дисковод выполняет функции чтения/записи. Диск установлен на шпинделе и вращается с высокой скоростью вокруг шпинделя.Когда дорожка проходит под головкой чтения/записи (также называемой магнитной головкой), данные могут быть прочитаны/записаны. Общие диски делятся на диски с фиксированной головкой (неподвижные головки) и диски с подвижной головкой. На каждой дорожке диска с фиксированной головкой имеется независимая магнитная головка, которая закреплена и специально отвечает за чтение/запись данных на этой дорожке. Головка подвижного головного диска (на фото выше) подвижна. На каждой поверхности диска имеется только одна магнитная головка (магнитная головка двунаправленная, поэтому можно читать и записывать переднюю и заднюю поверхности диска). Его можно перемещать с одной дорожки лица на другую. Все головки установлены на одной стреле, поэтому все головки на разных дисках двигаются одновременно (действие одинаковое). Когда диск вращается вокруг шпинделя, головка и вращающийся диск образуют цилиндр. Дорожки с одинаковым радиусом на каждом диске образуют цилиндр, который мы называем цилиндром. Следовательно, количество цилиндров равно количеству дорожек на диске.

Данные на диске должны быть однозначно идентифицированы трехмерным адресом: номер цилиндра, номер диска, номер блока (блока диска на дорожке). Чтение/запись указанных данных на диск требует следующих 3 шагов: (1) Во-первых, переместите рычаг, чтобы переместить головку к требуемому цилиндру в соответствии с номером цилиндра, этот процесс называется позиционированием или поиском. (2) Как показано на рис. 11.3 выше, на схематической диаграмме группы из 6 дисков все головки расположены на 10 дорожках на 10 поверхностях дисков (все головки двунаправленные). В это время трек на указанном диске определяется по номеру диска. (3) После определения поверхности диска диск начинает вращаться, и участок дорожки с заданным номером блока перемещается под магнитную головку. После трех вышеперечисленных шагов находится место хранения указанных данных. Теперь можно начинать операцию чтения/записи. Доступ к определенной части информации состоит из 3 частей времени:

Время поиска Ts: время, необходимое для выполнения шага (1) выше. Эта часть времени самая затратная, и максимум может достигать около 0,1 с.
Время задержки Tl: время, необходимое для выполнения шага (3) выше. Так как диск очень быстро вращается вокруг главного вала, то обычно она составляет 7200 об/мин (один из показателей производительности компьютерных винчестеров, а скорость вращения обычных винчестеров в домашних условиях вообще 5400 об/мин (ноутбук) и 7200 об/мин). Следовательно, один оборот обычно составляет около 0,0083 с.
Время передачи (время передачи) Tt: время передачи данных в память через системную шину, обычно байт (байт) передается около 0,02 мкс = 2 * 10 ^ (-8) с.

Данные чтения с диска основаны на дисковом блоке (блоке) в качестве базовой единицы. Все данные в одном блоке диска могут быть прочитаны одновременно. Стоимость дискового ввода-вывода в основном тратится на время поиска Ts. Поэтому мы должны стараться хранить соответствующую информацию в одном и том же блоке диска и на одной и той же дорожке. Или, по крайней мере, разместить на том же цилиндре или соседних цилиндрах, чтобы свести к минимуму количество движений головки вперед и назад при чтении/записи информации и избежать чрезмерного времени поиска.Ts. Поэтому при крупномасштабном хранении данных большой объем данных хранится на депозитном диске, и при чтении/записи блоков (блоков) на депозитном диске сначала необходимо позиционировать их по кусочку на диске, как эффективно поиск данных на диске требует разумной и эффективной структуры данных депозита.

хэш-индекс

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

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

Хэш-индексы будут иметь очень высокую производительность при выполнении тестов на равенство (равно или нет), но они бессильны в более сложных сценариях, таких как запросы сравнения и Order By.

B-Tree

B-дерево и B+дерево

существуетСтруктуры данных и алгоритмы / деревья поиска https://url.wx-coder.cn/9pnzgВ этом разделе мы представили базовую концепцию и реализацию B-дерева.Здесь мы продолжим анализировать, почему B-дерево больше подходит для реализации индексов базы данных, чем бинарные деревья поиска, такие как красно-черные деревья. В общем, сам индекс тоже очень большой, и хранить его весь в памяти невозможно, поэтому индекс часто хранится на диске в виде индексных файлов. В этом случае потребление дисковых операций ввода-вывода будет формироваться в процессе поиска по индексу, по сравнению с доступом к памяти потребление операций ввода-вывода на несколько порядков выше, поэтому важнейший показатель для оценки качества данных структура в качестве индекса — это асимптотическая сложность числа операций ввода-вывода на диске во время поиска. Другими словами, структура индекса организована таким образом, чтобы свести к минимуму количество обращений к диску в процессе поиска.

В соответствии с определением B-дерева можно знать, что для извлечения за раз необходимо посетить не более h узлов. Разработчики системы баз данных умело использовали принцип упреждающего чтения с диска, чтобы установить размер узла равным одной странице, чтобы каждый узел мог быть полностью загружен только одним вводом-выводом. Каждый раз, когда создается новый узел, он напрямую обращается к странице пространства, что гарантирует, что узел также физически хранится на странице. требуется для узла. При извлечении для извлечения требуется не более h-1 операций ввода-вывода (резидентная память корневого узла), а его асимптотическая сложность равна O(h)=O(log_dN)O(h)=O(log_dN) , на практике исходящая степень d — это очень большое число, обычно более 100, поэтому h очень мало (обычно не более 3). Очевидно, что в структуре красно-черного дерева h намного глубже. Поскольку логически близкие узлы (родительский и дочерний) могут быть физически далеко, локальность не может быть использована, поэтому асимптотическая сложность ввода-вывода красно-черного дерева также составляет O (h), что значительно менее эффективно, чем B-Tree.

B+Tree представляет собой вариант B-Tree и имеет более высокую производительность запросов, чем B-Tree.По сравнению с B-Tree он имеет следующие изменения:

Узел с m поддеревьями содержит m элементов (m-1 в B-дереве).
Узлы root и филиалов не держат данные только для индекса, все данные хранятся в узлах листа.
Все корневые узлы и ветви одновременно присутствуют в узере ребенка, это самый большой или наименьший элемент в узле дочернего элемента.
Листовые узлы будут содержать все ключевые слова и указатели на записи данных, а сами листовые узлы связаны в порядке возрастания в соответствии с размером ключевых слов.

Структуры B+Tree, обычно используемые в системах баз данных или файловых системах, оптимизированы на основе классических B+Tree с добавлением последовательных указателей доступа:

Как показано на рисунке выше, добавление указателя на соседний конечный узел к каждому конечному узлу B+Tree формирует B+Tree с последовательными указателями доступа. Целью этой оптимизации является повышение производительности интервального доступа.Например, на следующем рисунке, если вы хотите запросить все записи данных с ключами от 3 до 8, когда найдено 3, вам нужно только пройти узлы и указатели для одноразового доступа.Для всех узлов данных очень важна эффективность интервального запроса.

порядок индекса

Индексы B-деревьев хорошо работают для сканирования однорядных, диапазон или префикса, и они полезны только при поиске с использованием левого префикса индекса. Тем не менее, индексы B-деревьев имеют некоторые ограничения:

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

Поэтому порядок столбцов B-Tree очень важен, и приведенные выше правила использования связаны с порядком столбцов. Для практических приложений обычно необходимо создавать индексы с разными столбцами и разным порядком столбцов в соответствии с конкретными требованиями. Предположим, что есть индекс Index(A,B,C):

# 使用索引
A>5 AND A<10 - 最左前缀匹配
A=5 AND B>6 - 最左前缀匹配
A=5 AND B=6 AND C=7 - 全列匹配
A=5 AND B IN (2,3) AND C>5 - 最左前缀匹配，填坑

# 不能使用索引
B>5 - 没有包含最左前缀
B=6 AND C=7 - 没有包含最左前缀

# 使用部分索引
A>5 AND B=2 - 使用索引 A 列
A=5 AND B>6 AND C=2 - 使用索引的 A 和 B 列

Чтобы использовать индекс для сортировки результатов, порядок индекса должен соответствовать порядку в предложении ORDER BY, а порядок возрастания и убывания всех столбцов согласован (ASC/DESC). Если запрос объединяет несколько таблиц, в столбце ORDER BY есть ссылка только на первую таблицу (требуется последовательное СОЕДИНЕНИЕ).

# 使用索引排序
ORDER BY A - 最左前缀匹配
WHERE A=5 ORDER BY B,C - 最左前缀匹配
WHERE A=5 ORDER BY B DESC - 最左前缀匹配
WHERE A>5 ORDER BY A,B - 最左前缀匹配

# 不能使用索引排序
WHERE A=5 ORDER BY B DESC,C ASC - 升降序不一致
WHERE A=5 ORDER BY B,D - D 不在索引中
WHERE A=5 ORDER BY C - 没有包含最左前缀
WHERE A>5 ORDER BY B,C - 第一列是范围条件，无法使用 BC 排序
WHERE A=5 AND B IN(1, 2) ORDER BY C - B 也是范围条件，无法用 C 排序

LSM Tree

Метод индексирования базы данных B-Tree является основным методом построения индекса в традиционных реляционных базах данных.Однако BTree обычно имеет узкое место в пропускной способности операций записи, что требует большого объема случайных дисковых операций ввода-вывода.Очевидно, что большой объем случайных дисковых операций IO серьезно повлияет на скорость построения индекса. В тех случаях, когда данные индекса велики (например, объединенный индекс двух столбцов), скорость вставки является важным показателем влияния на производительность, в то время как операции чтения происходят относительно редко. Например, в случае отсутствия кеша B-Tree сначала необходимо выполнить чтение и запись с диска, чтобы прочитать страницу диска в память, затем изменить ее и, наконец, выполнить обратную запись ввода-вывода на диск.

LSM Tree использует стратегию разделения чтения и записи и отдает приоритет обеспечению производительности операций записи; его данные сначала хранятся в памяти, а затем их необходимо периодически сбрасывать на жесткий диск. LSM-Tree обеспечивает оптимальную производительность записи за счет вставки в память и последовательной записи на диск, потому что это значительно снижает количество обращений к диску, а один дисковый ввод-вывод может записывать несколько блоков индекса. HBase, Cassandra, RockDB, LevelDB, SQLite и т. д. — все это базы данных, которые строят индексы на основе LSM Tree; узлы дерева LSM Tree можно разделить на два типа: хранящиеся в памяти называются MemTable, а хранящиеся на диске — называется MemTable.SSTable.

Основная идея LSM-дерева — разделить деревья разного уровня. Взяв в качестве примера двухуровневое дерево, можно представить, что данные индекса состоят из двух деревьев, одно из которых находится в памяти, а другое — на диске. Дерево в памяти может быть такой структурой, как AVL Tree; поскольку размер данных отличается, нет необходимости жертвовать ЦП для достижения минимальной высоты дерева. Дерево, существующее на диске, является B-Tree.

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

После того, как листовые узлы, существовавшие на диске, будут объединены, старые данные не будут удалены, а будет записана копия данных на диск последовательно с данными в памяти. Это приведет к потере некоторого пространства, однако LSM-Tree предоставляет некоторые механизмы для освобождения этого пространства. Данные нелистовых узлов дерева на диске также кэшируются в памяти. Поиск данных сначала будет искать дерево в памяти, и если результаты не будут найдены, вместо этого будет искать дерево на диске. Существует очевидная проблема: если объем данных слишком велик, дерево на диске будет соответственно большим, и в результате скорость слияния будет ниже. Одним из решений является построение деревьев на каждом уровне, при этом деревья более низкого уровня имеют большие наборы данных, чем деревья верхнего уровня. Предполагая, что дерево в памяти равно c0, дерево на диске иерархическиc1, c2, c3, ... ck-1, ck. Порядок слияния такой(c0, c1), (c1, c2)...(ck-1, ck).

дальнейшее чтение

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