Экстент

Экстент (непрерывная область на диске) представляет собой последовательность логических блоков. Механизм экстентов используется несколькими файловыми системами и ядрами баз данных. Описатель экстента обычно состоит из трех полей: beginning, extent size, offset, где beginning («начало») — это адрес блока, с которого начинается экстент, extent size («размер экстента») — это количество блоков, а offset («сдвиг») — это смещение первого байта экстента относительно начала файла.

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

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

B+деревья

B+деревья широко используются в индексных структурах баз данных, обеспечивая быстрый и масштабируемый доступ к записям. Название «B+дерево» — сокращение от Balanced Tree («сбалансированное дерево»). Знак «+» указывает на то, что это модифицированная версия «исходного» B-дерева; она содержит указатели, которые провязывают между собой листья дерева, что помогает последовательному доступу.

B+деревья состоят из узлов двух различных типов: промежуточные узлы и концевые узлы (листья). Все узлы содержат в себе множества пар (ключ, указатель), упорядоченные по значению ключа в порядке возрастания. Указатели промежуточных узлов служат для ссылки на другие указатели промежуточных или концевых узлов, указатели концевых узлов — непосредственно на информацию. Ключ применяется для организации информации внутри B+дерева. В базах данных каждая запись имеет поле ключа, по значению которого различают записи одного и того же типа. B-деревья используют ключ для построения индекса записей баз данных, который позволяет сократить время доступа к ним. Сравнивая текущий ключ с ключом искомого узла, программа находит требуемую информацию.

Чтобы найти определенную запись, необходимо сделать следующее. Предположим, что мы ищем запись с определенным ключом — «K». Поиск следует начинать с корневого узла, а затем последовательно сканировать ключи, хранящиеся внутри. Узел сканируется до тех пор, пока не найден ключ со значением больше «K». Затем переходим к узлу (промежуточному или конечному, пока не известно точно, к какому), на который ссылается соответствующий указатель. После этого, если этот узел является промежуточным, операция повторяется. Наконец, найден конечный узел, который последовательно сканируется до тех пор, пока не найден требуемый ключ «K». Поскольку, для того чтобы найти нужный ключ, требуется извлечь меньшее число блоков, этот метод поиска имеет меньший уровень сложности, чем последовательное сканирование, при котором, в самом худшем случае, пришлось бы просмотреть все элементы.