к оглавлению

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

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

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

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

И наконец, на третьем уровне находится собственно основной файл.

Механизм доступа к записям по вторичному ключу при подобной организации записей весьма прост. На первом шаге мы ищем в области первого уровня заданное значение вторичного ключа, а затем по ссылке считываем блоки второго уровня, содержащие номера записей с заданным значением вторичного ключа, а далее уже прямым доступом загружаем в рабочую область пользователя содержимое всех записей, содержащих заданное значение вторичного ключа.

На рис. 9.11 представлен пример инвертированного списка, составленного для вторичного ключа «Номе]) группы» в списке студентов некоторого учебного заведения. Для более наглядного представления мы ограничили размер блока пятью записями (целыми числами).

Рис. 9.11. Построение инвертированного списка по номеру группы для списка студентов

Для одного основного файла может быть создано несколько инвертированных списков по разным вторичным ключам.

Следует отметить, что организация вторичных списков действительно ускоряет поиск записей с заданным значением вторичного ключа. Но рассмотрим вопрос модификации основного файла.

При модификации основного файла происходит следующая последовательность действий:

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

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

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

к оглавлению

(время поиска примерно 20 секунд)

Знаете ли Вы, почему "черные дыры" - фикция?
Согласно релятивистской мифологии, "чёрная дыра - это область в пространстве-времени, гравитационное притяжение которой настолько велико, что покинуть её не могут даже объекты, движущиеся со скоростью света (в том числе и кванты самого света). Граница этой области называется горизонтом событий, а её характерный размер - гравитационным радиусом. В простейшем случае сферически симметричной чёрной дыры он равен радиусу Шварцшильда".
На самом деле миф о черных дырах есть порождение мифа о фотоне - пушечном ядре. Этот миф родился еще в античные времена. Математическое развитие он получил в трудах Исаака Ньютона в виде корпускулярной теории света. Корпускуле света приписывалась масса. Из этого следовало, что при высоких ускорениях свободного падения возможен поворот траектории луча света вспять, по параболе, как это происходит с пушечным ядром в гравитационном поле Земли.
Отсюда родились сказки о "радиусе Шварцшильда", "черных дырах Хокинга" и прочих безудержных фантазиях пропагандистов релятивизма.
Впрочем, эти сказки несколько древнее. В 1795 году математик Пьер Симон Лаплас писал:
"Если бы диаметр светящейся звезды с той же плотностью, что и Земля, в 250 раз превосходил бы диаметр Солнца, то вследствие притяжения звезды ни один из испущенных ею лучей не смог бы дойти до нас; следовательно, не исключено, что самые большие из светящихся тел по этой причине являются невидимыми." [цитата по Брагинский В.Б., Полнарёв А. Г. Удивительная гравитация. - М., Наука, 1985]
Однако, как выяснилось в 20-м веке, фотон не обладает массой и не может взаимодействовать с гравитационным полем как весомое вещество. Фотон - это квантованная электромагнитная волна, то есть даже не объект, а процесс. А процессы не могут иметь веса, так как они не являются вещественными объектами. Это всего-лишь движение некоторой среды. (сравните с аналогами: движение воды, движение воздуха, колебания почвы). Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 13.06.2019 - 05:11: ЭКОЛОГИЯ - Ecology -> ПРОБЛЕМА ГЛОБАЛЬНОЙ ГИБЕЛИ ПЧЁЛ И ДРУГИХ ОПЫЛИТЕЛЕЙ РАСТЕНИЙ - Карим_Хайдаров.
12.06.2019 - 09:05: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров.
11.06.2019 - 18:05: ЭКСПЕРИМЕНТАЛЬНАЯ ФИЗИКА - Experimental Physics -> Эксперименты Сёрла и его последователей с магнитами - Карим_Хайдаров.
11.06.2019 - 18:03: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Андрея Маклакова - Карим_Хайдаров.
11.06.2019 - 13:23: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вячеслава Осиевского - Карим_Хайдаров.
11.06.2019 - 13:18: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Светланы Вислобоковой - Карим_Хайдаров.
11.06.2019 - 06:28: АСТРОФИЗИКА - Astrophysics -> К 110 летию Тунгуской катастрофы - Карим_Хайдаров.
10.06.2019 - 21:23: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Владимира Васильевича Квачкова - Карим_Хайдаров.
10.06.2019 - 19:27: СОВЕСТЬ - Conscience -> Высший разум - Карим_Хайдаров.
10.06.2019 - 19:24: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ЗА НАМИ БЛЮДЯТ - Карим_Хайдаров.
10.06.2019 - 19:14: СОВЕСТЬ - Conscience -> РУССКИЙ МИР - Карим_Хайдаров.
10.06.2019 - 08:40: ЭКОНОМИКА И ФИНАНСЫ - Economy and Finances -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
Bourabai Research Institution home page

Боровское исследовательское учреждение - Bourabai Research Bourabai Research Institution