Базы данных. Вводный курс
Страницы данных и идентификаторы кортежей
В каждой странице данных хранятся кортежи одной или нескольких таблиц. Фундаментальным понятием RSS является идентификатор кортежа (tuple identifier – tid). Гарантируется неизменяемость tid'а во все время существования кортежа в базе данных независимо от перемещений кортежа внутри страницы и даже при перемещении кортежа в другую страницу. Потребность в перемещении кортежей возникает по той причине, что кортеж, занесенный в некоторую таблицу базы данных, вообще говоря, во время своего существования может увеличиваться в размерах (если к этой таблице добавляется новое поле, или если в ней имеется хотя бы одно поле, типом данных которого являются строки символов переменного размера). Реально tid представляет собой пару <номер страницы, индекс описателя кортежа в странице>. При этом кортеж может реально располагаться в данной странице (рис. 12.1a) или в другой странице (рис. 12.1b).
Рис. 12.1. Идентификатор кортежа и расположение кортежа в странице данных
Как показывает рис. 12.1, в каждой странице данных имеются две области: область хранения описателей кортежей и область хранения самих кортежей. Один из остроумных приемов, примененных в System R, состоит в том, что обе эти области являются динамическими, т.е. в странице данных заранее не резервируется место под описатели кортежей. Легко видеть, что выделение фиксированной части страницы данных под описатели кортежей (вмещающей, скажем, k
описателей) потенциально привело бы к потери памяти в этой странице, поскольку при размещении в ней k
кортежей очень маленького размера пропадало бы место в области хранения кортежей, а при размещении p<k
крупных кортежей полностью заполнялась бы область хранения кортежей, но пропадало бы место в области описателей. Для динамического распределения памяти внутри страницы память на описатели кортежей выделяется вниз от начала страницы, а память для хранения кортежей – вверх от конца страницы.
Второй вариант хранения кортежей возникает в том случае, когда некоторый кортеж после своего создания был размещен системой в странице с номером N, а после обновления с увеличением размера перестал помещаться в этой странице, и система была вынуждена разместить его в странице с номером M.
Тогда исходный tid этого кортежа не изменится, но его описатель в странице N будет содержать не координаты кортежа в данной странице, а новый tid, указывающий на реальное положение кортежа в странице M. Легко видеть, что применение такого подхода позволяет ограничиться максимум одним уровнем косвенности (если данный кортеж в какой-то момент времени перестанет помещаться в странице M, и система переместит его в страницу P, то достаточно будет изменить косвенную ссылку на этот кортеж в странице N, и его исходный tid не изменится).
Поскольку допускается нахождение в одной странице данных кортежей разных таблиц, каждый кортеж должен, кроме содержательной части, включать служебную информацию, идентифицирующую таблицу, которой принадлежит данный кортеж. Кроме того, в System R (точнее, в языке SQL) допускается динамическое добавление полей к существующим таблицам. При этом реально происходит лишь модификация описателя таблицы в таблице-каталоге таблиц. В существующем кортеже таблицы новое поле возникает только при модификации этого кортежа, затрагивающей новое поле. Это позволяет избежать массовой перестройки хранимой таблицы при добавлении к ней новых полей, но, естественно, требует хранения при кортеже дополнительной служебной информации, определяющей реальное число полей в данном кортеже. (Заметим, что удалять существующие поля существующей таблицы в SQL System R не разрешалось.)
