22.Пояснити необхідність застосування індексів у базах даних, склад та структура індексів, хешування, бінарні дерева, b–дерева.

Индекс — объект БД, создаваемый с целью повышения производительности выполнения запросов. Таблицы в базе данных могут иметь большое количество строк, которые хранятся в произвольном порядке, и их поиск по заданному значению путем последовательного просмотра таблицы строка за строкой может занимать много времени. Индекс формируется из значений одного или нескольких столбцов таблицы и указателей на соответствующие строки таблицы и, таким образом, позволяет находить нужную строку по заданному значению. Ускорение работы с использованием индексов достигается в первую очередь за счёт того, что индекс имеет структуру, оптимизированную под поиск - например, балансированного дерева. Некоторые СУБД расширяют возможности индексов введением возможности создания индексов по выражениям. Например, индекс может быть создан по выражению  upper(last_name) и соответственно будет хранить ссылки, ключом к которым будет значение поля last_name в верхнем регистре. Кроме того, индексы могут быть объявлены как уникальные и как неуникальные. Уникальный индекс реализует ограничение целостности на таблице, исключая возможность вставки повторяющихся значений.

Существует два типа индексов: кластерные и некластерные.

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

Индексы физически могут быть реализованы различными структурами. Наиболее частоупотребимы B* деревья, B+ деревья, B-деревья и хеши.

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

B-дерево — с точки зрения внешнего логического представления, сбалансированное сильно ветвистое дерево во внешней памяти. Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же. Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков. С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, то есть каждому узлу дерева соответствует блок внешней памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру.Дерево характеризуют степенью t. В вершине может быть максимум 2t-1 и минимум t-1 элементов. Вершина содержащая n элементов имеет n+1 потомков или является терминальной(листовой).

Хеширование — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения (англ. message digest). Существует множество алгоритмов хеширования с различными характеристиками (разрядность, вычислительная сложность, криптостойкость и т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи.

Простейшими примерами хеш-функций могут служить контрольная сумма или CRC.

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

Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла. Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева. Узел дерева, не имеющий потомков, называется листом.