Таблицы

В данном разделе рассмотрены плоские таблицы с фиксированным числом столбцов. Примером такой таблицы может служить телефонный справочник:

Таблицу идентификаторов строит любой компилятор:

Мы не рассматриваем таблиц с двумя входами типа таблицы умножения (рис.30), в которых искомая величина лежит на перекрестии строки и столбца. Строку таблицы называют также записью или кортежем. Столбец также называют полем или атрибутом. Поле или группа полей, по которым выполняется поиск данных в таблице, называется ключом. Если в таблице не может суще­ство­вать более одной записи с данным значением ключа, то такой ключ называют первичным. Другие ключи называют непервичными или вторичными. В телефонном справочнике роль первичного ключа может играть, например, номер телефона. Фамилия не может быть первичным ключом, так как возможно существование одно­фамильцев. Все операции в таблице задаются по отношению к ключу, а выполняются над всей записью. К типичным операциям над таблицей относятся:

- включение: дана пара ключ - данные. Требуется включить запись в таблицу так, что впоследствии ее можно было найти по ключу.

- поиск. Дан ключ, требуется найти запись.

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

- удаление. Дан ключ, требуется найти и удалить запись.

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

- последовательные

- сортированные

- древовидные

- рассеянные (они же рандомизированные или hash – таблицы)