Эта статья взята из видео на Youtube, и я думаю, что оно относительно хорошее. Ссылка выглядит следующим образом:Woohoo. YouTube.com/watch?V=AZ просто…
содержание
- структура диска
- Как диски хранят данные
- что такое индекс
- Что такое многоуровневый индекс
- m-way дерево поиска
- B-tree: дерево поиска m-way + правила
- Операция вставки в B-дерево
- В+ дерево
структура диска
Проще говоря: по часовой стрелке диск состоит из множества секторов, пронумерованных от 0 до N. Снаружи внутрь диск состоит из нескольких дорожек, пронумерованных 0-N. Место пересечения сектора и дорожки называется блоком, и каждый блок имеет свой адрес, который может быть представлен (номер_дорожки, номер_сектора). Размер каждого блока одинаков, а конкретный размер зависит от реальной ситуации.Здесь мы предполагаем, что размер блока составляет 512 байт.
Одна вещь, которая должна быть очень ясной:Будь то операция чтения или операция записи, она выполняется блоками.
Внутри блока его можно увидеть как структуру массива с координатами от 0 до 511. Каждый байт имеет адрес, который называется смещением. Таким образом, мы можем представить каждый байт на диске в виде (номер_дорожки, номер_сектора, смещение).
В компьютере структуру диска можно представить так кратко.
Есть головка чтения-записи, и в каждый момент времени головка чтения-записи совмещена с одним из блоков на диске (номер_дорожки, номер_сектора). Sector_no можно изменить, повернув, а track_no можно изменить, растянув головку чтения/записи.
Еще один момент, который необходимо уточнить: ** Только данные на диске загружаются в ОЗУ (оперативное запоминающее устройство), прежде чем они могут быть использованы программой. ** Или, это действительно полезно для программы.
Как оптимизировать эффективность данных в оперативной памяти называется структурой данных, как оптимизировать эффективность данных на диске называется СУБД, и это то, что необходимо изучить большинству баз данных.
Как диск хранит данные (конкретные данные базы данных)
Теперь есть таблица сотрудников с этими полями, размер каждого поля такой, как показано на рисунке, а размер записи всего 128 байт.
Всего имеется 100 строк данных:
Каждый блок может хранить 4 строки данных. Для хранения этих 100 единиц данных требуется 25 блоков. Если нам нужно запросить один фрагмент данных сейчас, нам нужно запросить до 25 блоков.
что такое индекс
Мы создаем простой индекс с двумя полями: eid, представляющий идентификатор сотрудника, и указатель поля, указывающий на место хранения данных на диске. Каждая строка в empolyee имеет запись по индексу.
Так как же нам хранить этот индекс? Здесь мы предполагаем, что все они хранятся на диске (конечно, вы можете хранить их прямо в памяти). Итак, сколько блоков должен занимать этот индекс? Размер eid равен 10 байтам, а размер указателя — 6 байтам, поэтому индекс строки имеет размер 16 байтов. 100 индексов должны занимать 100*16/512 -> 4 блока.
Итак, теперь, чтобы запросить определенный фрагмент данных в таблице сотрудников, сколько блоков нужно запросить максимум? Ответ 4+1=5. Эффективность намного выше, чем раньше.
Что такое многоуровневый индекс
Теперь предположим, что имеется 1000 элементов данных, эти 1000 элементов данных займут 250 блоков, а индекс, упомянутый в предыдущем разделе, займет 40 блоков. Теперь, используя индекс для однократного запроса, требуется максимум 41 доступ к блоку. Теперь этот индекс больше не может соответствовать нашему стремлению к производительности, так можем ли мы построить индекс на основе индекса? То есть вторичный индекс?
Для вторичного индекса не обязательно записывать расположение каждого сотрудника на диске, а только расположение всех блоков в первичном индексе.Следовательно, вторичному индексу нужно 40 записей, то есть он должен занимать место в 2 блока. Такой вторичный индекс можно назвать разреженным индексом, и он не содержит расположение всех строк данных.
Теперь со вторичным индексом эффективность запроса составляет: 2 + 1 + 1 = 4 обращения к блоку.
Поскольку объем данных продолжает увеличиваться, для индекса второго уровня можно также установить индекс третьего уровня, а для индекса третьего уровня можно установить индекс четвертого уровня...
В то же время мы также хотим сделать следующее:Многоуровневые индексы могут автоматически создаваться и удаляться при изменении размера тома данных.Это приводит к главным героям: B-деревьям и B+-деревьям.
m-way дерево поиска
Двоичное дерево поиска: каждый узел имеет значение и имеет двух дочерних элементов.
Расширяя бинарное дерево поиска, каждый узел может хранить до m-1 значений индекса, и каждый узел может иметь m дочерних узлов, что является деревом поиска с m-путями.
На приведенном выше рисунке показано трехстороннее дерево поиска.
В следующем четырехстороннем дереве поиска каждый узел хранит до 3 значений индекса, 4 указателя на дочерние узлы и указатель Rp на расположение элемента данных.
Мы можем использовать это дерево поиска m-way в качестве индекса базы данных, однако есть некоторые проблемы с деревом поиска m-way:
Например, теперь есть три данных: 10, 20, 30, которые должны быть построены с помощью дерева поиска с 10 путями. Скорее всего, вы в конечном итоге построите дерево следующим образом:
В конце концов, это наихудший сценарий. Нам нужно заполнить каждый узел, прежде чем мы сможем создать следующий дочерний узел. В самом m-way дереве поиска такого принуждения нет, его можно вставлять по желанию.
B-tree: дерево поиска m-way + правила
B-дерево, на самом деле можно рассматривать как m-way дерево поиска + правила (как строить правила этого дерева).
правило:
- Каждый узел имеет не менее [m/2] потомков
- Корневой узел может иметь как минимум 2 дочерних узла.
- Все конечные узлы должны быть на одном уровне
- Процесс создания идет снизу вверх
Операция вставки в B-дерево
Значения: 10, 20, 40, 50. Построить 4-стороннее дерево поиска. Дерево поиска с 4 путями, что означает, что узел может иметь до 3 значений.
Это фактически создает вторичный индекс. Верх — это индекс второго уровня, а низ — индекс первого уровня. Каждый слой представляет собой первичный индекс.
Вставьте 60 и 70:
Затем вставьте 80, узел в правом нижнем углу не имеет пустой позиции, поэтому вам нужно создать новый узел, а затем поднять значение 70 до предыдущего слоя.
Вставка 30:
Вставка 35:
И т. д. и т. д.:
Рядом с каждым значением есть указатель на то, где хранятся данные.
В+ дерево
В дереве B+ не каждое значение имеет указатель на место хранения данных, он есть только у листовых узлов. Значение нелистового узла, копия которого находится на листовом узле. как показано на рисунке:
Это становится плотным индексом.