Использование индексов в базе данных
Индексирование в базах данных. Создание индекса, его типы, виды и структура. Индексы для последовательных файлов. Неупорядоченные и упорядоченные файлы. Типы хеширования, древовидные структуры для многомерных данных. Деревья квадрантов и их вершины.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 19.06.2015 |
| Размер файла | 2,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Пример бинарного дерева изображен на рис.23 [9], а конкретный экземпляр этой структуры показан на рис.24 [9]. Обратите внимание, что нижняя строчка на рис.23 - последовательный набор - представляет собой обычный индекс. Он содержит указатель на каждую запись в файле (хотя для краткости данные и адреса записей были опущены). Также заметьте, что элементы последовательного набора сгруппированы по три. Записи в каждой группе физически упорядочены, и каждая группа связана со следующей посредством связного списка, как можно видеть на рис.24.
Взгляните на индексный набор на рис.23. Верхняя запись содержит дна значения.45 и 77. Следуя левой линии связи (к записи с относительным номером 2), мы можем обратиться к записям, значения ключей которых меньше или равны 45; следуя средней линии связи, мы можем обратиться к записям, значения ключей которых больше 45 и меньше или равны 77; наконец, следуя правой линии связи (к записи с относительным номером 4), мы можем обратиться к записям, значения ключей которых больше 77.
Рис.23. Общая структура простого бинарного дерева
Рис. 24. Пример бинарного дерева, со структурой, соответствующей рисунку 23
Аналогичным образом, на следующем уровне имеется три значения и три указателя на каждый элемент индекса. Всякий раз, когда мы спускаемся на уровень ниже, мы сужаем область своего поиска. Например, если от верхней записи мы проследуем по левой линии связи, а от следующего уровня - по правой линии, мы сможем обратиться ко всем записям, значения ключей которых больше 27, но меньше или равны 45. На первом уровне мы исключили все записи, значения ключей которых больше 45.
Бинарные деревья по определению являются сбалансированными. Это значит, что все записи находятся на одинаковом расстоянии от верхней записи индексного набора. Это свойство бинарных деревьев обусловливает их эффективность, хотя алгоритмы вставки и удаления записей оказываются сложнее, чем для обычных деревьев (которые могут быть несбалансированными), поскольку для того, чтобы при этих операциях сохранить все записи на одинаковом расстоянии, может потребоваться модификация нескольких записей. [9]
Древовидные структуры для многомерных данных
Теперь рассмотрим ряд индексных структур, особенно полезных при обработке запросов в диапазонах значении и поиске объектов, ближайших по отношению к заданному:
индексы с несколькими ключами (multiple-key indexes);
kd-деревья (kd-trees);
деревья квадрантов (quad trees);
R-деревья (R-trееs).
Три первые структуры предназначены для представления множеств точек. R-дерсвья обычно используются с целью описания множеств областей пространства, хотя находят применение и для отображения множеств точек.
Индексы с несколькими ключами
Предположим, что схема отношения содержит атрибуты, представляющие значения координат элементов данных многомерного пространства, и необходимо обеспечить эффективную поддержку запросов в диапазонах значений (range queries) координат либо процедур поиска объектов, наиболее близких к заданному (nearesl-neighbor search). Одно из простых решений связано с использованием индекса индексов или, говоря в более общем смысле, древовидной схемы, в которой вершины каждого уровня являются индексами для определенного атрибута.
Основная идея проиллюстрирована на рис. 25 [6] на примере двух атрибутов. "Корнем дерева" служит индекс для первого атрибута. В подобной роли может выступать индекс любого из традиционных типов, таких как В-дерево или хеш-таблица-Индекс связывает значение ключа поиска (содержимое компонента первого атрибута) с указателем на некоторый индекс для другого атрибута. Если V - содержимое компонента первого атрибута, отыскав элемент со значением V ключа поиска в первом индексе и проследовав в "направлении" указателя, связанного с этим элементом, мы "придем" к индексу, представляющему подмножество точек, первые координаты которых равны V, а вторые содержат произвольные значения.
Рис. 25. Пример многоуровнего индекса с несколькими ключами kd-деревья
kd-дерево (kd-tree или k-dimensional search Iree) - это структура, служащая для представления информации в оперативной памяти и обобщающая модель бинарных деревьев поиска на случаи многомерных данных. Вначале мы обсудим основные характеристики схемы kd-дсрева, а затем расскажем об особенностях ее реализации в контексте модели блоковых вторичных хранилищ данных, kd-дерево представляет собой бинарное дерево, с корневой и промежуточными вершинами которого ассоциированы атрибут а, представляющий некоторую размерность данных, и определенное значение V этого атрибута, расщепляющее множество точек данных на два подмножества: точкам одного подмножества отвечают значения атрибута я, меньшие V, a точкам другого - значения а, равные или большие V. Атрибуты в пределах одного уровня дерева одинаковы, а в соседних уровнях - различны: при движении от корневой вершины дерева "вниз" по уровням промежуточных вершин все атрибуты-размерности циклически замешают друг друга.
В классическом kd-дереве, как и в дереве бинарного поиска, с вершинами связаны точки данных. Мы, однако, незначительно изменим схему таким образом, чтобы адаптировать ее к особенностям модели блокового хранилища данных:
каждой промежуточной вершине поставлены в соответствие некоторый атрибут, конкретное "разделяющее" значение этого атрибута и указатели-дуги, адресующие левую и правую дочерние вершины;
листья дерева представляют блоки, способные содержать такое количество записей, какое обусловлено физическим объемом блока.
Деревья квадрантов
В дереве квадрантов (quad tree) каждая промежуточная вершина соответствует определенному квадранту пространства данных - прямоугольной двумерной области либо k-мерному параллелепипеду, если количество измерений равно k. Как и при рассмотрении всех остальных структур данных, описываемых в этой главе, мы сосредоточим внимание на случае двух измерений. Если количество точек, принадлежащих квадранту, ниже допустимого максимума, квадрант следует воспринимать как вершину-лист дерева, представляемую соответствующим блоком. Если же, напротив, количество точек слишком велико, квадрант интерпретируется как промежуточная (вначале - корневая) вершина с четырьмя дочерними вершинами, отвечающими частным квадрантам.
R-деревья
R-дерево (R-lree, или region tree - дерево областей) - это структура данных, наследующая многие свойства модели В-дерева в применении к многомерной информации. Напомним, что вершина В-дерева содержит подмножество значений ключа, делящих числовую ось на сегменты. Каждая точка оси может принадлежать только одному сегменту. Отыскание заданной точки в В-дереве труда не составляет: так как точка расположена на оси, представляемой вершиной В-дерева, мы можем определить единственный сегмент (дочернюю вершину), которые позволят сузить область поиска и в конце концов либо найти точку, либо убедиться, что ее не существует.
R-дерево, с другой стороны, представляет информацию в виде 2 - или А-мсрных областей данных (data regions). Корневая (или промежуточная) вершина R-дерева соответствует некоторой внутренней области (interior region), или просто "области", которая обычно не является областью данных. Вообще говоря, область может иметь любую форму, хотя на практике, как правило, используются области прямоугольных или иных простых форм. Вершина R-дерева вместо ключевых значений содержит подобласти (subregions), описывающие содержимое дочерних вершин. [6]
индекс база хеширование файл
Заключение
Само по себе, построение таблиц и обращение к их содержимому - настолько простая и понятная вещь, что многие, освоив основные приемы, попросту перестают изучать синтаксис построения и оптимизации таблиц более глубоко.
А между тем, одна только индексация таблиц порой поднимает производительность в несколько раз.
В данном реферате рассмотрены все типы и виды индексов, а так же приведены примеры и способы создания индексов в SQL и определение индексации было изложено, но постараюсь ещё раз на простом примере объяснить, что такое индексация и для чего она нужна.
Вспомните любую публичную библиотеку. Пусть детскую или даже школьную. Помните зал со стеллажами книг? И даже если вы были очень давно в библиотеке, вы прекрасно знаете, что все книги в этом уважаемом заведении расставлены не просто так, не в порядке их поступления в библиотеку (как поступают данные в базу), а по каким-то правилам. Обычно, книги разносят по темам, авторам и по алфавиту.
Я думаю, излишне объяснять, зачем все это делается, и почему библиотекари так ревностно следят за порядком размещения книг на стеллажах. Но обратите ваше внимание на сравнительную эффективность поиска в такой структурированной системе, которой, кстати, обычно пренебрегают при построении и использовании компьютерных баз данных.
Предположим, вы в библиотеке ищите книгу "Как выращивать цветы в сухой местности". Если вы начнете просто перебирать все книги в библиотеке, то у вас на это уйдет не один день или даже не один месяц, если это крупная библиотека.
Но если вы знаете автора или год или тему книги, то, подойдя к соответствующим стеллажам, вы найдете издание за несколько минут, а то и секунд. Как, собственно, это и бывает в библиотеке.
То же самое происходит и с нашей базой данных, когда мы её индексируем. С помощью индексов мы ускоряем работу нашего компьютера, не заставляя его перебирать все данные в нашей базе, а всего-навсего обращаться к нужным данным. Полагаю, что польза индексации очевидна.
Список используемой литературы
1. Малыхина М.П. Базы данных: основы, проектирование, использование. - Спб.: БХВ - Петербург, 2004. - 528с.: ил.
2. Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. - 133с.: ил.
3. Калабухов Е.В. Базы данных, знаний, и экспертные системы: Курс лекций - Минск: БГУИР, 2007. - 290с.: ил.
4. Хомоненко А.Д. Базы данных. Учебник для высших учебных заведений, под редакцией проф. Санкт Петербург, Корона, 2004г. - 726с.: ил.
5. Саймон А.Р. Стратегические технологии баз данных: менеджмент на 2000 год: Пер. с англ. / Под ред. И с предисл. М.Р. Когаловского. - М.: Финансы и статистика, 1999.
6. Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. - 1088 с.: ил. - Парал. тит. англ.
7. Dmitry. Burmistrov, Иван Игнатьев. Индексирование в базах данных [Электронный ресурс] // База знаний кафедры ИКТ: [сайт]. [2009]. URL: http://wiki. auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,09 (дата обращения 29.03.2012).
8. Коннолли, Томас, Бегг, Каролин. Базы данных. Проектирование, реализация, сопровождение. Теория и практика.3-е изд.: Пер. с англ. - М.: "Вильямс", 2003. - 1440с.: ил. - Парал. тит. англ.
9. Кренке Д. Теория построения баз данных.8-е изд., Спб.: Питер, 2003. - 800с.: ил.
10. Диго С.М., Базы данных: проектирование и использование: Учебник. - М.: Финансы и статистика, 2005. - 592с.: ил.
Приложения
Приложение 1
Таблица понятий
|
№ |
Понятие (термин) |
Определение |
Источник |
|
|
1 |
База данных |
это именованная совокупность данных, отражающая состояние объектов и их отношений в рассматриваемой предметной области, или иначе БД - это совокупность взаимосвязанных данных при такой минимальной избыточности, которая допускает их использование оптимальным образом для одного или нескольких приложений в определенной предметной области. БД состоит из множества связанных файлов. |
Малыхина М.П. Базы данных: основы, проектирование, использование. - Спб.: БХВ - Петербург, 2004. |
|
|
2 |
Индексированный файл |
это основной файл, содержащий данные отношения, для которого создан индексный файл |
Малыхина М.П. Базы данных: основы, проектирование, использование. - Спб.: БХВ - Петербург, 2004. |
|
|
3 |
Индексный файл |
это файл особого типа, в котором каждая запись состоит из двух значений: данных и указателя |
Малыхина М.П. Базы данных: основы, проектирование, использование. - Спб.: БХВ - Петербург, 2004. |
|
|
4 |
Индекс [index] |
это структура данных, отображающая значения поискового ключа в адреса объектов поиска; это специальные структуры данных, создаваемые для повышения производительности базы данных |
Марков А.С., Лисовский К.Ю. Базы данных. Введение в теорию и методологию: Учебник. - М.: Финансы и статистика, 2004. Крёнке Д. Теория и практика построения баз данных.9-е изд. - Спб.: Питер, 2005. |
|
|
5 |
Вторичный индекс [secondary index] |
это индекс по вторичному ключу; это индекс, построенный не по первичному ключу, позволяет ускорить операции выборки для запросов, выполняющих фильтрацию не по полям первичного ключа |
Марков А.С., Лисовский К.Ю. Базы данных. Введение в теорию и методологию: Учебник. - М.: Финансы и статистика, 2004. Калабухов Е.В. Базы данных, знаний, и экспертные системы: Курс лекций - Минск: БГУИР, 2007. |
|
|
6 |
Главный индекс [master index] |
это индекс высшего уровня в иерархии индексной организации данных |
Марков А.С., Лисовский К.Ю. Базы данных. Введение в теорию и методологию: Учебник. - М.: Финансы и статистика, 2004. |
|
|
7 |
В-дерево |
это дерево, которое содержит три уровня: корневую вершину, промежуточные вершины и листья, хотя способно включать в себя и произвольное количество уровней |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
8 |
Бинарное дерево |
это индекс, состоящий из двух частей: последовательного набора (sequence set) и индексного набора (index set) |
Крёнке Д. Теория и практика построения баз данных.9-е изд. - Спб.: Питер, 2005. |
|
|
9 |
Последовательный набор |
представляет собой индекс, содержащий указатели на все записи в файле. Этот индекс физически упорядочен, обычно по назначению первичного ключа. |
Крёнке Д. Теория и практика построения баз данных.9-е изд. - Спб.: Питер, 2005. |
|
|
10 |
Индексный набор |
это иерархический индекс для последовательного набора |
Крёнке Д. Теория и практика построения баз данных.9-е изд. - Спб.: Питер, 2005. |
|
|
11 |
Индекс дорожек [traks index] |
это область индексно-последовательного файла, представляющая собой низший уровень системы его индексов и содержащая таблицу адресов дорожек цилиндра и максимальных значений ключей записей, размещенных на этих дорожках |
Марков А.С., Лисовский К.Ю. Базы данных. Введение в теорию и методологию: Учебник. - М.: Финансы и статистика, 2004. |
|
|
12 |
одноуровневый индекс |
это индекс, который непосредственно ссылается на данные, а не на другие индексные структуры |
Калабухов Е.В. Базы данных, знаний, и экспертные системы: Курс лекций - Минск: БГУИР, 2007. |
|
|
13 |
Многоуровневый индекс [multilevel index] |
это структура в виде сбалансированного дерева, имеющая два уровня иерархии или более. Корень такого дерева - главный индекс (индекс высшего уровня) |
Марков А.С., Лисовский К.Ю. Базы данных. Введение в теорию и методологию: Учебник. - М.: Финансы и статистика, 2004. |
|
|
14 |
Первичный индекс [primary index] |
это ведущий индекс, индекс по первичному ключу; это поле или группа полей, однозначно определяющих запись, т.е. значения первичного индекса уникальны |
Марков А.С., Лисовский К.Ю. Базы данных. Введение в теорию и методологию: Учебник. - М.: Финансы и статистика, 2004. Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. |
|
|
15 |
Составной индекс [concatenated] |
это индекс, аргументом которого является комбинация значений атрибутов |
Марков А.С., Лисовский К.Ю. Базы данных. Введение в теорию и методологию: Учебник. - М.: Финансы и статистика, 2004. |
|
|
16 |
Индексация [indexing, subscriping] |
это метод, обеспечивающий возможность обращения к элементу массива с помощью указания массива и выражений, определяющих местоположение этого элемента в массиве |
Марков А.С., Лисовский К.Ю. Базы данных. Введение в теорию и методологию: Учебник. - М.: Финансы и статистика, 2004. |
|
|
17 |
Индексирование [indexing] |
1. Использование индексов в базе данных.2. Процесс описания содержания документов и запросов в терминах информационно-поискового языка; назначение документу набора ключевых слов, отражающих его смысловое содержание |
Марков А.С., Лисовский К.Ю. Базы данных. Введение в теорию и методологию: Учебник. - М.: Финансы и статистика, 2004. |
|
|
18 |
Индексы в виде В-деревьев |
Представляют собой эффективный доступ для запросов диапазонов значений, за исключением случаев, когда количество подходящих строк становится слишком большим. |
К. Дж. Дейт. Введение в системы баз данных = An Introduction to Data base systems - 7 издание: Пер. С англ. - М: Издательский дом "Вильямс", 2001 |
|
|
19 |
Индексы в виде битовых отображений |
Предположим, что в индексированной таблице Т содержится n строк. Тогда индекс в виде битового отображения для столбца С таблицы Т будет содержать вектор из n бит для каждого значения в домене столбца С и установленный бит будет соответствовать строке R, если в её столбце С будет содержаться соответствующее значение. |
К. Дж. Дейт. Введение в системы баз данных = An Introduction to Data base systems - 7 издание: Пер. С англ. - М: Издательский дом "Вильямс", 2001 |
|
|
20 |
Кэш-индексы |
это индексы, которые эффективны для доступа к конкретным строкам, а не к диапазонам. |
К. Дж. Дейт. Введение в системы баз данных = An Introduction to Data base systems - 7 издание: Пер. С англ. - М: Издательский дом "Вильямс", 2001 |
|
|
21 |
Мультитабличные индексы |
это индексы, которые позволяют повысить производительность операции соединения и ускорить проверку ограничений целостности для нескольких таблиц. По существу элемент мультитабличного индекса содержит указатели на строки в нескольких таблицах вместо простых указателей на строки в одной таблице |
К. Дж. Дейт. Введение в системы баз данных = An Introduction to Data base systems - 7 издание: Пер. С англ. - М: Издательский дом "Вильямс", 2001 |
|
|
22 |
Булевы индексы (индексы выражений) |
Булев индекс указывает, для каких строк определенной таблицы определенное логическое выражение будет истинным |
К. Дж. Дейт. Введение в системы баз данных = An Introduction to Data base systems - 7 издание: Пер. С англ. - М: Издательский дом "Вильямс", 2001 |
|
|
23 |
Функциональные индексы |
функциональные индексы индексируют строки таблицы не на основе значений в этих строках, а на основе результата применения к этим значениям некоторой функции |
К. Дж. Дейт. Введение в системы баз данных = An Introduction to Data base systems - 7 издание: Пер. С англ. - М: Издательский дом "Вильямс", 2001 |
|
|
24 |
Гибридная индексная структура |
это структура, в которой дерево индекса разбивается на несколько поддеревьев, а доступ управляется некоторой хеш-функцией |
Саймон А.Р. Стратегические технологии баз данных: менеджмент на 2000 год: Пер. с англ. / Под ред. И с предисл. М.Р. Когаловского. - М.: Финансы и статистика, 1999 |
|
|
25 |
Простой индекс |
это индекс, построенный по значениям одного поля |
Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. |
|
|
26 |
Сложный индекс |
это индекс, построенный по значениям двух и более полей |
Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. |
|
|
27 |
Candidat |
это кандидат в первичный ключ или альтернативный ключ |
Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. |
|
|
28 |
Unique (уникальный тип индекса) |
это тип индекса, который допускает повторяющиеся значения в поле, по которому он построен, но на экран будет выводиться только одна первая запись из группы записей с одинаковым значением индексного поля |
Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. |
|
|
29 |
Regular (регулярный тип индекса) |
это тип индекса, который не накладывает никаких ограничений на значения индексного поля и на вывод записей на экран |
Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. |
|
|
30 |
Primary |
это один из индексов, удовлетворяющий требованиям индекса типа Candidat может быть выбран в качестве первичного ключа |
Базы данных. Учебник для высших учебных заведений, под редакцией проф.А.Д. Хомоненко, Санкт Петербург, Корона, 2004г. |
|
|
31 |
Одноиндексный файл |
это индексный файл, который хранит только один индекс |
Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. |
|
|
32 |
Мультииндексные файлы |
это индексные файлы, которые хранят много индексов |
Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. |
|
|
33 |
Тег |
это каждый индекс, который хранится в мультииндексном файле |
Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. |
|
|
34 |
Структурный мультииндексный файл |
это индексный файл, который имеет одинаковое имя с таблицей, которой он принадлежит |
Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. |
|
|
35 |
Индексное выражение |
это имя поля (или полей), по значениям которого надо построить индекс |
Иштерякова, Т.И. Базы данных: Курс лекций/ Т.И. Иштерякова - Оренбург: ГОУ ВПО ОГУ, 2009. |
|
|
36 |
Несоставной индекс |
это индекс, в котором ключ состоит только из одного поля записи |
Калабухов Е.В. Базы данных, знаний, и экспертные системы: Курс лекций - Минск: БГУИР, 2007. |
|
|
37 |
Плотный индекс |
это индекс, в котором число индексных записей равно числу записей данных, одна индексная запись ссылается только на одну запись данных |
Калабухов Е.В. Базы данных, знаний, и экспертные системы: Курс лекций - Минск: БГУИР, 2007. |
|
|
38 |
Неплотный индекс |
это индекс, в котором число индексных записей меньше числа записей данных, индекс указывает либо на первую запись в определенной группе, либо на страницу с определенной группой записей данных |
Калабухов Е.В. Базы данных, знаний, и экспертные системы: Курс лекций - Минск: БГУИР, 2007. |
|
|
39 |
Индекс кластеризации |
это индекс, в котром файл данных последовательно упорядочивается по неключевому полю, и на основе этого неключевого поля формируется поле индексации, поэтому в файле может быть несколько записей, соответствующих значению этого поля индексации. Неключевое поле называется атрибутом кластеризации. |
Российский новый университет - РосНОУ. Базы Данных. Индексирование. http://rosnoun. narod.ru/bd/17. htm |
|
|
40 |
индексированно - последовательные файлы |
это отсортированные файлы данных с первичным индексом |
Российский новый университет - РосНОУ. Базы Данных. Индексирование. http://rosnoun. narod.ru/bd/17. htm |
|
|
41 |
иерархия узлов |
это иерархия, в которой каждый узел, за исключением корня (root), имеет родительский (parent) узел, а также один, несколько или ни одного дочернего (child) узла |
База знаний кафедры ИКТ http://wiki. auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,09 |
|
|
42 |
Глубина дерева |
это максимальное количество уровней между корнем и листом |
База знаний кафедры ИКТ http://wiki. auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,10 |
|
|
43 |
Степень (degree) (или порядок (order)) дерева |
это максимально допустимое количество дочерних узлов для каждого родительского узла |
База знаний кафедры ИКТ http://wiki. auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,11 |
|
|
44 |
Структурный индексный файл |
это индексный файл, который обеспечивает реализацию всех индексов одной таблицы и имеет имя, совпадающее с именем самой таблицы, и расширение CDX |
Базы данных. Учебник для высших учебных заведений, под редакцией проф.А.Д. Хомоненко, Санкт Петербург, Корона, 2004г. |
|
|
45 |
Ключ поиска (search key) |
1. это поля, на основе значений которых индекс конструируется; 2. это атрибуты, заданные значения которых используются в качестве критерия поиска (с применением индекса) определенных групп кортежей отношений |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
46 |
Плотная индексная структура (dense) |
это индексная структура, где каждой записи файла данных отвечает определенный элемент файла индекса |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
47 |
Разреженная индексная структура (sparse) |
это структура, в которой файл индекса содержит указатели только на некоторые записи файла данных |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
48 |
Последовательный файл |
это файл, отсортированный по значениям атрибутов индекса |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
49 |
Разреженные индексы (sparse index) |
это индексы, которые хранят по одному ключевому элементу для каждого блока файла данных |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
50 |
Хеш-таблицы (hash tables) |
это первичные индексы, в которых ключ поиска определяет сегмент (bucket), которому принадлежит определенная запись |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
51 |
Хеш-функция (hash function) |
это функция, принимающая в качестве параметра значение ключа поиска (в данном случае уместно называть его хеш-ключом) и вычисляющая число в интервале от 0 до В-1, где В-количество сегментов (buckets) |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
52 |
Обращенный (inverted) индекс |
это индекс, который сочетает в себе все индексы и используется совместно с промежуточным уровнем групп - сегментов указателей |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
53 |
Сбалансированное (balancer) В-дерево |
это В-дерево, в котором длины всех путей от корневой (root) вершины до любой из вершин-листьев (leaves) равны |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
54 |
Хеширование (hashing - перемешивание) |
это технология быстрого прямого доступа к физической записи на основе заданного значения поля перемешивания (хеш-ключ) |
Калабухов Е.В. Базы данных, знаний, и экспертные системы: Курс лекций - Минск: БГУИР, 2007. |
|
|
55 |
Статическое хеширование |
это размер хеш-файла задается один раз при его создании и больше не изменяется (фиксируется пространство хеш-адресов) |
Калабухов Е.В. Базы данных, знаний, и экспертные системы: Курс лекций - Минск: БГУИР, 2007. |
|
|
56 |
Динамическое хеширование |
позволяет динамическое изменение размера хеш-файла при добавлении в него записей |
Калабухов Е.В. Базы данных, знаний, и экспертные системы: Курс лекций - Минск: БГУИР, 2007. |
|
|
57 |
Точечный индекс (bitmap index) для некоторого поля F |
это коллекция битовых векторов длины n, по одному на каждое возможное значение поля F |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
58 |
Cеточные файлы (grid files) |
это многомерная версия хеш-таблиц |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
59 |
Раздельные хеш-функции (partioned hash functions) |
это альтернативный способ реализации механизма хеш-таблиц в применении к многомерным данным |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
60 |
Индексы с несколькими ключами (multiple-key index) |
это структуры, в которых индексные значения одного кдюча связаны со значениями ключа индексов следующего уровня и т.д. |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
61 |
kd-деревья (kd-trees) |
это обобщение модели В-дерева в приложении к множествам точек |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
62 |
Деревья квадрантов (quad trees) |
это деревья, каждая дочерняя вершина которых представляет один из квадрантов площади, описываемой родительской вершиной |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
63 |
R-деревья (R-trees) |
это обобщение модели В-дерева для представления множеств областей пространства |
Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс - М.: Вильямс, 2003. |
|
|
64 |
Хеш-ключ |
это поле, являющееся ключевым полем файла |
База знаний кафедры ИКТ http://wiki. auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,09 |
|
|
65 |
Поле хеширования (hash field) |
это поле, значения которого являются параметрами хеш-функции |
База знаний кафедры ИКТ http://wiki. auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,10 |
|
|
66 |
Метод доступа |
это действия, выполняемые при сохранении или извлечении записей из файла |
База знаний кафедры ИКТ http://wiki. auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,11 |
|
|
67 |
Организация файла |
это физическое распределение данных файла по записям и страницам на вторичном устройстве хранения |
База знаний кафедры ИКТ http://wiki. auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,12 |
|
|
68 |
Неупорядоченные файлы |
это файл, в котором записи размещаются в том порядке, в котором они в него вставляются |
База знаний кафедры ИКТ http://wiki. auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,13 |
|
|
69 |
Упорядоченные файлы |
это файл, записи в котором можно отсортировать по значениям одного или нескольких полей и таким образом образовать набор данных, упорядоченный по некоторому ключу |
База знаний кафедры ИКТ http://wiki. auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,14 |
|
|
70 |
Буквенный индекс [alphabetic code, alphabetic notation] |
это индекс, использующий отдельные буквы или сочетание букв алфавита |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
71 |
Цифровой индекс [numerical code, numerical notation] |
это индекс, использующий отдельные цифры, числа, сочетания цифр или их комбинации |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
72 |
Десятичный индекс [decimal code, decimal classification code] |
это цифровой индекс, составленный на основе десятичной системы счисления |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
73 |
Алфавитно-цифровой индекс [alphanumeric code] |
это смешанный индекс, состоящий из букв и цифр |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
74 |
Смешанный индекс [mixed code, mixed notation] |
это индекс, состоящий из разнородных знаков, например, из букв различных алфавитов, букв и цифр и т.п. |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
75 |
Интервальный индекс [interval index] |
это индекс, значения которого определяются некоторой областью, например, диапазоном от 3 до 12 |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
76 |
Гипериндекс [hyperindex] |
это высший уровень индекса индексной организации баз данных, принятый в некоторых СУБД (наряду с главным и нормальным индексами) |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
77 |
Нормальный индекс [normal index] |
это подмножество ключей базы данных, соответствующих конкретному значению поля, объявленного дескриптором (признаком поиска). Используется в четырехуровневой системе индексов СУБД, например, - ADABAS |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
78 |
Вспомогательный (дополнительный) индекс [additional index, auxiliary code, auxiliary classification number] |
это индекс, являющийся дополнением к главному (основному) и отражающий дополнительные признаки индексируемого текста, документа и т.п. или относящийся к вспомогательной системе классификации |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
79 |
Авторский знак [author mark, author notation, author number] |
это индекс, обозначающий автора произведения, используемый при расстановке и поиске книг в библиотеках |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
80 |
Кеттерский знак [cutter number] |
это авторский знак, определяемый по "Авторской таблице" Ч. Кеттера |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
81 |
Расстановочный индекс [location mark, location number] |
это индекс, используемый для расстановки и поиска книг, документов и т.п. в библиотеке или фонде |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
82 |
Каталожный индекс [catalog classification mark, catalog classification number] |
это индекс, используемый для расстановки и поиска карточек в каталоге |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
83 |
Индекс каталога [catalog index] |
это старший индекс в библиотечной организации данных |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
84 |
Индекс массива [array index] |
это индекс, присваиваемый массиву документов или данных для его идентификации |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
85 |
Индекс файла [index number] |
это в некоторых операционных системах (например, UNIX) номер индексного дескриптора файла и др. |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
86 |
Кумулятивная индексация [cumulative indexing] |
это индексация, предусматривающая присвоение одному адресу несколько индексов |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
87 |
Однорядная индексация [pure notation system] |
это индексация, в которой использованы т. н. "однорядные" знаки: буквы одного алфавита, цифры одной системы счисления и т.п. |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
88 |
Одноуровневая индексация |
это индексация с использованием одноуровневых индексов |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
89 |
Многоуровневая индексация |
это индексация с использованием многоуровневых индексов |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
90 |
Смешанная индексация [mixed notation system] |
это индексация, в которой использованы различные знаки: буквы, цифры и т.п. |
ИНДЕКСИРОВАНИЕ И КОДИРОВАНИЕ ДАННЫХ http://www.gpntb.ru/win/book/1/Doc18.html |
|
|
91 |
свертка (folding) |
это один из методов создания хеш-функции, основан на выполнении некоторых арифметических действий над различными частями поля хеширования |
База знаний кафедры ИКТ http://wiki. Auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,12 |
|
|
92 |
Хеширование с применением остатка от деления |
это метод, в котором используется функция MOD, которой передается значение поля |
База знаний кафедры ИКТ http://wiki. Auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,13 |
|
|
93 |
Расширяемое хеширование |
Этот метод предусматривает изменение размеров блоков по мере роста базы данных, но это компенсируется оптимальным использованием места |
База знаний кафедры ИКТ http://wiki. Auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,15 |
|
|
94 |
Метод цепочек |
это самый очевидный путь решения проблемы. В случае, когда элемент таблицы с индексом, который вернула хеш-функция, уже занят, к нему присоединяется связный список |
База знаний кафедры ИКТ http://wiki. Auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,16 |
|
|
95 |
Открытая адресация |
это путь решения проблемы, который заключается в формулировании правила, согласно которому по данному ключу определяется пробная последовательность, т.е. последовательность позиций таблицы, которые должны быть просмотрены при вставке или поиске ключа K |
База знаний кафедры ИКТ http://wiki. Auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,17 |
|
|
96 |
Линейная адресация |
это простейшая схема открытой адресации, известная как линейная адресация (линейное исследование, linear probing) использует циклическую последовательность проверок h (K), h (K - 1), …, 0, M - 1, M - 2, …, h (K) + 1 и описывается следующим алгоритмом. Он выполняет поиск ключа K в таблице из M элементов. Если таблица не полна, а ключ отсутствует, он добавляется |
База знаний кафедры ИКТ http://wiki. Auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,18 |
|
|
97 |
Квадратичная и произвольная адресация |
Вместо постоянного изменения на единицу, как в случае с линейной адресацией, можно воспользоваться следующей формулой: h = h + a2, где a - это номер попытки |
База знаний кафедры ИКТ http://wiki. Auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608, 19 |
|
|
98 |
Адресация с двойным хешированием |
Этот алгоритм выбора цепочки очень похож на алгоритм для линейной адресации, но он проверяет таблицу несколько иначе, используя две хеш - функции h1 (K) и h2 (K). Последняя должна порождать значения в интервале от 1 до M - 1, взаимно простые с М |
База знаний кафедры ИКТ http://wiki. Auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608, 20 |
|
|
99 |
Хеширование паролей |
это метод, позволяющей пользователям запоминать не 128 байт, то есть 256 шестнадцатиричных цифр ключа, а некоторое осмысленное выражение, слово или последовательность символов, называющуюся паролем |
База знаний кафедры ИКТ http://wiki. Auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,21 |
|
|
100 |
Коллизия (collision) |
это такая ситуация, в которой предположим, что существуют два различных ключа k1 и k2 (k1 k2) такие, что h (k1) =h (k2). Когда запись с ключом k1 вводится в таблицу, она вставляется в позицию с индексом h (k1). Но когда хешируется ключ k2, получаемая позиция является той же позицией, в которой хранится запись с ключом k1. Ясно, что две записи не могут занимать одну и ту же позицию. |
База знаний кафедры ИКТ http://wiki. Auditory.ru/%D0%91%D0%94: %D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9608,22 |
Размещено на Allbest.ru
Подобные документы
Минимизация количества операций ввода-вывода данных как цель упорядочения расположения данных на диске (структуры хранения), используемые в данном процессе методы. Принципы обработки файлов. Назначение индексов и индексирования. Техники хеширования.
реферат [22,7 K], добавлен 21.06.2016Точечные и пространственные данные. Отображение в одномерном пространстве, сеточна органзация. K-d-деревья, тетрарные деревья и K-D-B-деревья. Требования к структурам многомерных данных. Свойства точечного пространства. Объекты с переменной размерностью.
презентация [125,9 K], добавлен 11.10.2013Сущность и функциональные особенности баз данных, их классификация и типы, внутренняя структура и элементы. Модели данных, хранящихся в базах: иерархическая, сетевая, реляционная, многомерная, объектно-ориентированная. Виды запросов и типы таблиц.
дипломная работа [66,7 K], добавлен 06.01.2014Понятия основных компонентов базы данных Access. Таблицы, отчеты, макросы и модули, форма, запросы к базе и их виды. Типы данных. Создание базы данных "Кадры". Создание таблицы в режиме конструктора. Использование мастера подстановок для создания связей.
курсовая работа [818,0 K], добавлен 10.03.2016Создание однотабличных баз данных и ключей, индексирование однотабличной БД с помощью конструктора таблиц Table Designer в SQL Server Management Studio. Понятие и назначение индексов кластерного и некластерного типов, инструкция по их созданию в БД.
лабораторная работа [684,9 K], добавлен 01.12.2011Типы изображений (черно-белые, полутоновые, цветные) и их форматы. Устройства, создающие цифровые изображения, и их параметры. Применение и характеристики методов сжатия изображений. Поиск по содержимому в базах данных изображений. Структуры баз данных.
презентация [360,4 K], добавлен 11.10.2013Построение инфологической модели данных каталога магазина цифровых дисков. Окно создания новых файлов. Типы данных в Visual FoxPro. Список типов индекса. Структура таблиц, связи между ними. Настройка внешнего вида формы. Выбор поля для сортировки данных.
курсовая работа [4,3 M], добавлен 24.09.2013Возможности системы управления базами данных Access. Структура простейшей базы данных: свойства ее полей, типы данных, безопасность и режим работы. Определение связей между таблицами в базе данных. Использование запроса на выборку, макроса и отчетов.
курсовая работа [1,7 M], добавлен 05.12.2010Исследование особенностей организации мультимедийной информации. Абстрактные представления. Языки запросов для мультимедийных данных. Индексирование в структурированных мультимедийных базах данных. Анализ мультимедиа-интерфейса для описания содержимого.
презентация [174,6 K], добавлен 11.10.2013Создание баз данных с помощью Transact-SQL. Специализированные типы данных. Обеспечение целостности ссылок. Преимущества хранимых процедур. Синтаксис запроса на создания триггера. Фиксированные серверные роли. Предоставление прав на объекты в базе данных.
лабораторная работа [2,2 M], добавлен 12.09.2012
