3.2. Линейный список

Линейный (последовательный) список – последовательность записей базы данных, сформированная по некоторым логическим принципам. Например, в таблице, содержащей информацию о поступлении товаров в магазин, сведения о каждой поставке представляют собой записи, вводимые в базу данных в хронологическом порядке и размещаемые в физической памяти последовательно друг за другом (табл. 3.1):

Таблица 3.1

Сведения о поставках товаров в магазин

Номер накладной	Название товара	Артикул	Количество	Дата поставки
37	Костюм	500	50	10.12.05
54	Сапоги	200	75	10.12.05
18	Туфли	100	120	11.12.05
60	Костюм	500	35	11.12.05
28	Костюм	300	20	12.12.05
74	Костюм	400	50	12.12.05
80	Туфли	100	100	12.12.05

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

3.3. Инвертированный список

Инвертированные списки позволяют существенно ускорить процесс поиска необходимой информации по сравнению с линейными списками. Это достигается с помощью упорядочивания (сортировки) записей исходного списка по значениям данных в одном из неключевых полей. Инвертирование исходного списка можно выполнить для отдельных (частичное инвертирование) или всех (полное инвертирование) неключевых полей исходного списка.

Предположим, что значения номеров накладных в поле Номер накладной таблицы Сведения о поставках товаров в магазин (см. табл. 3.1) являются уникальными, т.е. данное поле является первичным ключом таблицы. Инвертированный список по полю Артикул будет выглядеть следующим образом (табл. 3.2):

Таблица 3.2

Сведения о поставках товаров в магазин

Номер накладной	Название товара	Артикул	Количество	Дата поставки
18	Туфли	100	120	11.12.05
80	Туфли	100	100	12.12.05
54	Сапоги	200	75	10.12.05
28	Костюм	300	20	12.12.05
74	Костюм	400	50	12.12.05
37	Костюм	500	50	10.12.05
60	Костюм	500	35	11.12.05

Полученный инвертированный список позволяет выполнять быстрый поиск информации по данным в поле Артикул, не требуя просмотра всех записей (например, при поиске сведений о товарах, артикулы которых менее 300, достаточно извлечь и рассмотреть только первые четыре записи).

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