Тема_8 (1122356), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Кузнецов. Базы данных.34 Организация данныхОсновные понятия, цели и общая организация System R (30)Организация внешней памяти в базах данных System R (9) Страницы данных (8) Тогда исходный tid этого кортежа не изменится, но его описатель встранице N будет содержать не координаты кортежа в данной странице, а новый tid, указывающий на реальное положение кортежа в странице M12.11.2009С.Д. Кузнецов. Базы данных.35 Организация данныхОсновные понятия, цели и общая организация System R (31)Организация внешней памяти в базах данных System R (10) Страницы данных (9) Легко видеть, что применение такого подхода позволяет ограничитьсямаксимум одним уровнем косвенности если данный кортеж в какой-то момент времени перестанет помещатьсяв странице M, и система переместит его в страницу P, то достаточнобудет изменить косвенную ссылку на этот кортеж в странице N, и егоисходный tid не изменится12.11.2009С.Д.

Кузнецов. Базы данных.36 Организация данныхОсновные понятия, цели и общая организация System R (32)Организация внешней памяти в базах данных System R (11) Страницы данных (10)Поскольку допускается нахождение в однойстранице данных кортежей разных таблиц,каждый кортеж должен, кроме содержательнойчасти, включатьслужебную информацию, идентифицирующую таблицу,которому принадлежит данный кортежКроме того, в System R (точнее, в языке SQL)допускается динамическое добавление полей ксуществующим таблицамПри этом реально происходит лишьмодификация описателя таблицы в таблицекаталоге таблиц12.11.2009С.Д.

Кузнецов. Базы данных.37 Организация данныхОсновные понятия, цели и общая организация System R (33)Организация внешней памяти в базах данных System R (12) Индексы и кластеризация таблиц(1)На основе наличия уникальных,обеспечивающих почти прямой доступ ккортежам и не изменяемых во времясуществования кортежей tid'ов в System Rподдерживаютсядополнительные управляющие структуры – индексыКаждый индекс определяется на одном илинескольких полях таблицы, значения которыхсоставляют его ключ, и позволяет производитьпрямой поиск по ключу кортежей (их tid'ов) ипоследовательное сканирование таблицы по индексу,начиная с указанного ключа, в порядке возрастания илиубывания значений ключа12.11.2009С.Д.

Кузнецов. Базы данных.38 Организация данныхОсновные понятия, цели и общая организация System R (34)Организация внешней памяти в базах данных System R (13) Индексы и кластеризация таблиц(2)Некоторые индексы при их создании могутобладать атрибутом уникальностиВ таком индексе не допускаются дубликаты ключаЭто единственное средство SQL System R указаниясистеме первичного ключа таблицы (фактически,набора первичного и всех возможных ключей таблицы).Для организации индексов в System Rприменяется техника B+-деревьевболее подробно B+-деревья рассматриваются вэтой лекции позже12.11.2009С.Д.

Кузнецов. Базы данных.39 Организация данныхОсновные понятия, цели и общая организация System R (35)Организация внешней памяти в базах данных System R (14) Индексы и кластеризация таблиц(3)Каждый индекс занимает отдельный наборстраниц, номер корневой страницызапоминается в описателе индексаИспользование B+-деревьев позволяет достичьэффективности при прямом поиске, посколькуони в силу своей сильной ветвистости обладаютнебольшой глубинойКроме того, B+-деревья сохраняют порядокключей в листовых блоках иерархии, чтопозволяет производить последовательноесканирование таблицы в порядке возрастанияили убывания значений полей, на которыхопределен индекс12.11.2009С.Д.

Кузнецов. Базы данных.40 Организация данныхОсновные понятия, цели и общая организация System R (36)Организация внешней памяти в базах данных System R (15) Индексы и кластеризация таблиц(4)Фундаментальное свойство B+-деревьевавтоматическая балансировка деревадопускает произведение лишь локальныхмодификаций индекса при переполнениях иопустошениях страниц индексаSystem R была первой системой, в которой дляорганизации индексов использовались B+деревьяЭту традицию соблюдает большинствореляционных систем, возникших после System R12.11.2009С.Д.

Кузнецов. Базы данных.41 Организация данныхОсновные понятия, цели и общая организация System R (37)Организация внешней памяти в базах данных System R (16) Индексы и кластеризация таблиц(5)Видимо, наиболее важной особенностью физическойорганизации баз данных в System R является возможностьобеспечения кластеризации связанных кортежей одной илинескольких таблицПод кластеризацией кортежей понимается физическиблизкое расположение (в пределах одной страницы данных)логически связанных кортежейОбеспечение соответствующей кластеризации позволяетдобиться высокой эффективности системы при выполнениивыделенного класса запросовВ силу большой важности понятия кластеризации в System Rи ее развитиях рассмотрим историю вопроса болееподробно12.11.2009С.Д.

Кузнецов. Базы данных.42 Организация данныхОсновные понятия, цели и общая организация System R (38)Организация внешней памяти в базах данных System R (17) Индексы и кластеризация таблиц(6)В окончательном варианте System R существуеттолько одно средство определения условийкластеризации таблицыобъявить до заполнения таблицы один (и только один)индекс, определенный на полях этой таблицы,кластеризованнымТогда, если заполнение таблицы кортежамипроизводится в порядке возрастания илиубывания значений полей кластеризации (взависимости от атрибутики индекса),система физически располагает кортежи в страницахданных в том же порядке12.11.2009С.Д.

Кузнецов. Базы данных.43 Организация данныхОсновные понятия, цели и общая организация System R (39)Организация внешней памяти в базах данных System R (18) Индексы и кластеризация таблиц(7)Кроме того, в каждой странице данныхкластеризованной таблицы оставляетсянекотороерезервное свободное пространствоПри последующих вставках кортежей в такуютаблицу система стремится поместить каждыйкортеж в одну из страниц данных, в которых уженаходятся кортежи этой таблицыс такими же (или близкими) значениями полейкластеризации12.11.2009С.Д.

Кузнецов. Базы данных.44 Организация данныхОсновные понятия, цели и общая организация System R (40)Организация внешней памяти в базах данных System R (19) Индексы и кластеризация таблиц(8)Естественно, поддерживать идеальнуюкластеризацию таблицы можно только доопределенного предела,пока не исчерпается резервная память в страницахДалее этого предела степень кластеризациитаблицы начинает уменьшаться, и длявосстановления идеальной кластеризациитаблицы требуетсяфизическая реорганизация таблицыее можно произвести средствами SQL12.11.2009С.Д. Кузнецов.

Базы данных.45 Организация данныхОсновные понятия, цели и общая организация System R (41)Организация внешней памяти в базах данных System R (20) Индексы и кластеризация таблиц(9)Очевидным преимуществом кластеризациитаблицы является то, что при последовательномсканировании кластеризованной таблицы сиспользованием кластеризованного индексапотребуетсяровно столько чтений страниц данных с внешнейпамяти,сколько страниц занимают кортежи этой таблицыСледовательно, при правильно выбранныхкритериях кластеризации запросы, связанные сзаданием условий на полях кластеризацииможно выполнить почти оптимально12.11.2009С.Д.

Кузнецов. Базы данных.46 Организация данныхОсновные понятия, цели и общая организация System R (42)Организация внешней памяти в базах данных System R (21) Индексы и кластеризация таблиц В(10)ранних версиях System R существовал еще один способфизического доступа к кортежам таблицы и, соответственно,еще один способ указания условия кластеризации сиспользованием так называемых связей (links)На уровне физического представления связь – этофизическая ссылка (tid) из одного кортежа на другой кортеж не обязательно одной таблицыВ языке SEQUEL (до того момента, когда его стали называтьSQL) существовали средства определения связей виерархической манере: можно было объявить некоторую таблицу родительской поотношению к той же или другой таблице-потомку12.11.2009С.Д. Кузнецов.

Базы данных.47 Организация данныхОсновные понятия, цели и общая организация System R (43)Организация внешней памяти в базах данных System R (22) Индексы и кластеризация таблиц(11)При этом указывались поля родительскойтаблицы и таблицы-потомка, в соответствии созначениями которых образовывалась иерархияПравила построения были очень простымипроводились связи от кортежа родительской таблицыко всем кортежам таблицы-потомка с теми жезначениями полей связыванияНа самом деле, все кортежи таблицы-потомка собщим значением полей связыванияобразовывали кольцевой список, на которыйпроводилась одна связь из соответствующегокортежа родительской таблицы12.11.2009С.Д. Кузнецов.

Базы данных.48 Организация данныхОсновные понятия, цели и общая организация System R (44)Организация внешней памяти в базах данных System R (23) Индексы и кластеризация таблиц(12)Следует заметить, что этот способиспользования механизма связейподдерживался в ранних версиях SEQUELВ интерфейсе RSS System R этого периодадопускалась возможность произвольногопроведения связей без учета совпадениязначений полей связыванияТем самым, в системе в целом неиспользовались все возможности RSS, которыес избытком превосходили потребности организациииерархических бинарных связей по совпадению полейсвязывания12.11.2009С.Д. Кузнецов. Базы данных.49 Организация данныхОсновные понятия, цели и общая организация System R (45)Организация внешней памяти в базах данных System R (24) Индексы и кластеризация таблиц Для(13)одной таблицы допускалось создание многих связей:кортеж таблицы мог быть родителем нескольких иерархий ивходить в несколько других иерархий в качестве потомкаПри этом одна связь могла быть объявленакластеризованной Тогда система стремилась поместить в одну страницуданных все кортежи одной иерархии При этом, естественно, использовалась возможностьразмещения в одной странице данных кортежей несколькихтаблицОсновной смысл такой кластеризации заключался ввозможности оптимизации выполнения некоторых запросов, включающих (экви)соединение двух связанных таблиц всоответствии со значениями полей связывания12.11.2009С.Д.

Кузнецов. Базы данных.50 Организация данныхОсновные понятия, цели и общая организация System R (46)Организация внешней памяти в базах данных System R (25) Индексы и кластеризация таблиц В(14)более поздних публикациях, посвященных System R,упоминания о механизме связей исчезли, из чего можнозаключить, что разработчики отказались от егоиспользованияДумается, что основными причинами отказа отиспользования связей были следующиеВо-первых, средства построения связей, обеспечиваемыеRSS, были очень низкого уровня, гораздо более низкого, чемсредства поддержания индексов Если при занесении, удалении или обновлении кортежа RSSобеспечивала автоматическую коррекцию всех индексов, тодля коррекции связей требовалось выполнить ряддополнительных обращений к RSS, из-за чего времявыполнения этих операций, конечно12.11.2009С.Д.

Характеристики

Список файлов лекций