Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Структура хранения на основе индексирования предпологает использовать двух хранимых файлов.
В файле с индексами названия городов всегда упорядочены по алфавиту. И фактически есть риды(RID) соотвествующие записи файла поставщиков. Например:
Представим себе файл с данными, т.е таблица с поставщиками, там есть определенное колличество записей. Риды S1,S2 и так далее.
Файл городов: Файл с данными:
|
London |
ID |
|
|
Paris |
ID |
|
|
... |
ID |
|
|
… |
… |
|
|
S1 |
Смит |
London |
|
S2 |
Ли |
Paris |
|
S3 |
... |
…. |
|
S4 |
.... |
..... |
В индексном файле записи упорядочены по алфавиту, а в файле с данными записи распологаются как есть.Они могут быть упорядоченны не по файлу городов, а по номеру или фамилии поставщика. Но нам допустим надо по городу. Файл городов в этом случае называется индексным файлом, состоящим из двух колонок. Ну а файл таблица( в физическом смысле файл, или в логическом смысле файл, как это в SQL серверах) называется индексированным .
Фактически для того чтобы найти сведения быстро в таблице, первоначально считывается индексный файл, он поскольку всегда состоит из двух колонок, то он может быть относительно малым( а таблица может быть достаточно широкой). Загружается в память(индексный файл). Так как записи упорядочены по алфавиту, то быстро находиться по алфавиту методом двоичного поиска( он быстрый). Когда у нас данные индексированны от маленького значения до большого, фактически первый раз ищется половина, смотрим попали или не попали. Если не попали, то следущую пополам , если не попали опять следущую и так далее. Всего надо 10 шагов чтобы в файле из 1024 записей в порядке возрастания, или убывания найти нужную запись. Если бы искали по порядку то в худшем случае оказалось бы 1024 поиска. Скорость поиска по индексному файлу очень велика, и чем больше записей тем быстрее, вместо последовательного поиска по всем записям нужной записи.
Иногда индексный файл называют инвертированным списком. Очень удобны такие инвертированные списки когда они делаются по ключевому полю, по Primary Key. Очень эффективны и быстро работают. В принципе могут быть две стратегии поиска поставщиков ,например, из города London. В файле поставщиков найти все записи, названия городов которых являются London.Или сначала в файле городов найти все значения с London, а затем по указателям найти записи. Во втором случае получается гораздо быстрее. Правда есть время, затрачиваемое на считывание файла городов. Если эти файлы соизмеримы то выйгрыша нет, для маленьких табличек до 300 записей смысла индексы делать нет, потому что таблица с малым числом строк всегда загружается в виде страницы в память и что по индексу искать, что искать по памяти одинаково.
Если доля поставщиков из London очень мала, то такой файл эффективен (индексированный файл), если их доля велика то этот файл будет часто включаться, тогда выйгрыш от использования индексного файла начинает теряться. Индексы всегда хороши когда число искомых записей не превышает 10-15 процентов. Когда число искомых записей от 20% и выше то можно искать по прямому поиску.
Все записи про London идут друг за другом, и если нашлись несколько записей, идущих подряд, то ясно их положение, здесь они быстро считываются, и эти идентификаторы указывают на нужные записи. Если бы мы не упорядочевали, то London может встречаться где угодно и поиск будет долгим. Нужно будет просматривать всю таблицу.
Таким образом индексы позволяют избежать полного просмотра таблиц, котроый снижает существенно производительность. Снижает производительность не только конкретного клиента, который смотрит и перебирает всю таблицу, но и других, т.к сеть перегружается, буфер у сервера тоже перегружается, т.е тратяться у системы большие ресурсы и другие клиенты не могут их использовать. Сервер часто считывает данные, запись за записью диск только работает на одного человека.
Недостаток использования индексов заключается в том, что если их много, то после обновления данных в таблицах(просто обновления, удаления, добавления записей) индексы должны перестраиваться. Чем больше индексов, тем больше перестроек. В руководстве SQL сервер говориться так : “на одну таблицу не более 16 идексов”. После 16 быстродействие не гарантируется, т.е до 16 индексов переиндексацию сервер обеспечивает относительно быстро, а дальше производительность сильно падает.
Если индексирование сделанно по первичному ключу. То индекс называется первичным .В противном случае он называется вторичным, если по всем другим колонкам, например по городам, по каким нибудь рейтингам, и тд. Если индекс сделан по первичному ключу, то он еще в дополнение называется уникальным , потому что повторяющихся значений по первичному ключу в принципе быть не может. В файле городов он не может быть уникальным, т.к городов проживания может быть много (у многих клиентов могут быть одинаковые города).
Индексы могут использоваться для двух целей:
Варианты создаваемых индексов.
Хранимый файл может иметь один индекс ,как в нашем расмотренном случае, и хранимый файл может иметь несколько индексов, который сделаны так что они могут быть раздельными или совместными. Если индексов полей два и более, то индекс может быть сделан по каждому полю отдельно, или может быть сделан совместный, так называемый составной индекс. Т.е когда идет комбинация полей, он называется составным. Например, если бы у каждого поставщика деталей был какой-то статус(число какое-то), то мы могли бы искать не просто поставщиков из города London, а поставщиков из города London по какому то статусу, или рейтингу (рейтинг на основе стабильности работы поставщика, качестве деталей и тд) . Тогда в колонке индексов может храниться смешанная информация, данные о двух колонках, например о городах одновременно с рейтингами. Фактически будет две дополнительные колонки помимо идентификатора. Комбинированный индекс в этом случае может работать при поиске по двум полям одновременно, либо по первому полю. Точнее так сказать: если индекс содержит несколько колонок, то он может хорошо использоваться по всем трем колонкам, по первым двум колонкам, и по первой колонке. По второй и третьей, или просто третьей искать нельзя. Т.е если индекс составной из трех колонок, то он хорошо используется по всем трем, с первой по вторую, и по первой колонке. Отдельно по второй колонке работать не может.
Особенности создания и приминения индексов.
1) В ряде СУБД размер составного индекса ограничевается. (размер –колличество бит в строке). В SQL сервере 900 бит. С СУБД Oracle нельзя упорядочивать данные в нескольких колонках в разных направлениях(в некоторых СУБД можно, в некоторых нельзя) . В Fox Pro можно создать составной индекс, данные в котором упорядоченны в разных направлениях(одни по убыванию, другие по возрастанию). Но в Oracle только в одну сторону.
2) Для повышения производительности целесообразно размещать таблицы индексов в различных сегментах. Создаваемых на разных дисках. Тогда чтение и запись таблицы индексов может идти параллельно.
Надо отметить что СУБД в процессе работы само принимает решение какой из индексов, имеющийся у таблицы использовать. Если индексов несколько, СУБД само подберет нужный индекс.Это происходит чаще всего на основе суммарной информации (распределения данных в таблице). Бывает случаи когда расчитывается число различных значений индекса внутри индекса, отнесенных к среднему колличеству записей(т.е страниц). В колонке городов может быть записей 1000 а городов всего 10. На каждый город идет по 100 записей.
Информацию, на основе которой выбирают тот или иной индекс называют статистикой. В некоторых СУБД называют статистикой тенденции или эвристической статистикой, или статистикой эвристики. Но общее название это статистика, статистика расположения записей в той или иной таблице. Эти статистики не обнавляются, с обнавлением таблиц автоматически.Они обнавляются переодически. На их обновление нужно время, нужно расчитать все данные о таблицах и расчитать дополнительную информацию, которая в базе данных храниться, чтобы потом можно было использовать тот или иной индекс. Фактически сбор этой статистики инициирует администратор специальными командами, которые есть у сервера( т.е есть команды которые заставляют сервер создавать статистики для всего подряд). Это администратор может делать во вне урочное время, если же таблицы слишком сильно подвержены изменению, то эти статистики могут запаздывать, и сервер будет выбирать не те индексы которые надо для поиска данных. Чем лучше работает администратор, чем чаще проводит статистику, тем лучше работает сервер по поиску записи.
В СУБД Oracle предусмотрена возможность сегментирования таблиц большого размера вместе с индексами. Получается локальный индекс на какую-то часть таблицы(его размер становиться меньше). При считывании данных считывается не весь индекс, который может быть большим, а только локальный, что повышает быстродействие.
Кроме того в СУБД Oracle предусмотрена возможность создания индекса с обратным порядком.Что позволяет избежать конкуренции за доступ к последней странице. Когда в базе данных, которая является файлом есть логический файл в каком то колличестве. То фактически когда добавляются данные в таблицу, они не могут записаться где-то посередине файла, они все стремяться в конец файла при записи, в каждой таблице данные стремяться записаться в конец физического файла. В этом случае возникает конкуренция на ввод-вывод на последнюю страницу, но если сделать файл с обратным порядком, то некоторые таблицы могут пробиться в ту часть таблицы (особенно при кластерных индексах), где начальная сторона, и начало таблицы, если обратный порядок сделан, и таким образом конкуренция снижается. Тогда так называемый плотный индекс очень велик, и его считывание занимает достаточно большое время. Можно использовать многоуровневые или разряженные индексы. Что собственно сегодня и приминяется.
Неплотное индексирование.
Для поиска нужной записи используется RID. Но на самом деле SQL серверы работают не с записями, а со страницами. Считывается каждый раз страница, а внутри страницы ищется нужая запись. А раз так то на самом деле RID( Record идентификатор) можно заменить на идентификатор страниц. Поскольку на странице может умещаться несколько сот записей, то фактически общий индекс может быть уменьшен. Т.е считывается из памяти страница равная 1 Кбайту, 2 или 4(короче до 8 Кбайт), потом поиск нужной записи происходит не на диске а в оперативной памяти, поиск в оперативной памяти в 1000 раз быстрее, таким образом поиск сокращается. Вместо указателей на запись можно использовать указатели страниц.
Например, если говорить о городах, то страница , где расположены все поставщики: London, Paris и тд. (в зависимости от того как выбирается).
Такой индекс называется неплотным (sparse). Если в файле поставщиков выполнена кластеризация по какому-то полю, например по номеру поставщика, а также по нему создан индекс, то номера все хранить и не требуется. По скольку в этом случае получается: на каждой странице храниться какое то колличество записей, упорядоченных в порядке возрастания этого номера. Например, идентификатор будет на 100, на 200, на 300, на 400, а номера поставщиков будут на отдельной странице находиться, т.е если они там физически упорядоченны, что делается при кластеризации, то индекс достаточно указать на страницу( обычный индекс), а на странице они все будут находиться подряд( 101, 102 и тд). И поиск там не является проблемой.
Многоуровневые индексы.
Для ускорения просмотра больших индексов, часто делают индекс для индекса. Тогда индексный файл очень большой, и его приходиться частями загружать в оперативную память, и это тоже долго. Тогда если есть индексный файл, то фактически делается другой уровень.
…..
…..
….
……
…….
…….
…….
……
…..
Как только мы смотрим по символьному полю, или по числовому, более понятно на символьном поле. Допустим на A, B, C города, но все города на A (букву А) для них нужно считать не весь этот индекс, а только его часть. Т.е сначала считать индекс A потом, страницу городами на А.
Индекс для индекса позволяет ускорить процесс поиска, и в этом случае такой индекс называют многоуровневым. Индексов на индекс можно делать достаточно много, но обычно больше 3 ярусов не делают.
Вторичные индексы.
1) Часто для повышения быстродействия выборки данных, приходиться создавать несколько индексов для одной таблицы, большинство из которых является вторичными.( поскольку уникальный-один, остальные все вторичные).Фактически вторичный индекс выполняет те же самые функции что и первичный(он используется для поиска данных). Отличается от первого тем, что не может предсказать расположение данных. (например когда мы говорили в примере неплотного индекса, что они индексируют страницу, а страница упорялочена, и понятно где будет следующий индекс). Поэтому вторичные индексы не могут предсказать расположение подряд городов(если упорядочение идет по номерам), или например рейтинг, или фамилию поставщика( так как данные расположены неупорядоченно).
Т.е первичный индекс помимо того что позволяет искать, может предсказать где расположена следущая запись, вторичные этого делать не могут.
2) Вторичные индексы часто бывают сдубленны. Первичный индекс делается по Primary Key, по номеру, номера как правило должны быть уникальными, и там используются все записи, а по вторичному индексу(например по файлу городов) там могут быть дубли, городов всегда меньше, чем людей которые там проживают.
Формально можно использовать многоуровневые вторичные индексы, в этом случае часто на втором уровне могут попадаться дубликаты.
Поиск документов и обращенные индексы.
Для поиска документов среди WEB используются обращенные индексы. По существу это индексы, состоящие из большого числа полей, т.е по одному булевому значению для каждого слова, и когда тот или иной Yandex, Google, Yahoo и тд ищут они просматривают таблицы( первоначально для них составляются таблицы, где галочками отмечается если то что нужно или нет на определенной веб странице) по этим индексам, и смотрят есть ли галочки или нет, и эти страницы считавают.
Поэтому чем больше сайтов проиндексированно, тем эта таблица длинее и шире(больше слов используется). Т.е таблицы огромные, они просматриваются и ставятся булевые галочки, есть это слово(которое ищем) или нет.
Поэтому те поисковые системы, которые проиндексируют больше сайтов, у них таблица по длине и ширине больше.
Таким образом получают обращенные индексы.
Структуры типа B(балансированное Balance Tree) дерева.
Это наиболее распространенные в наше время индексы, для сверх больших баз данных. Фактически это многоуровневые индексы, правда сделанные не потипу индекс на индекс, как мы рассматривали первоначально.
Суть создания такого индекса такова, чтобы за 2, 3 считывания можно было находить нужную запись. Как это делается:
Есть какой то корневой индекс Root( в нем номера – 23 , 31, 44 , они очень разряжены). У них есть идентификация, указатели.
Все номера деляться на три группы, сначала большая разряженность, потом все чаще и чаще.
Каждый отдельный блок проэктируется таким образом, чтобы он занимал на диске размер, равный кластеру диска (от 1 до 8 Кбайт). В среднем один блок должен занимать ровно страницу памяти.
Размещается N указателей, и N+1 на следущую страницу, или соседний блок(все это в одном уровне).
До половины указателей в таком индексе резервируется для будущих записей. Чтобы индекс сильно не переделывать.
Если ключ это четырех байтное целое, а указатель это обычно 8 байт, то блок размером 4096 байт может включать примерно N=340 значений ключа.( 4N+8(N+1) <4096).
Такая система(такой индекс) типа B дерева, автоматически поддерживает необходимое колличество уровней, и обеспечивает автоматическое заполнение указателей, когда появляется новая запись.
Стоимость дисковых операций обычно считается пропорциональной числу блоков.
Поиск в таком балансированном дереве, когда обычно проверяется не более трех блоков, считается что он эффективнее чем бинарный поиск(когда каждый раз пополам делили).
Недостаток такой балансированной структуры заключается в том, что при большом числе именений, даже запас 50% бывает не хватает. Некоторые из сегментов начинают переполняться(каждый из сегментов – 4096 байт, но записи не равномерно заполняются, какие-то сегменты быстрее заполняются, какие-то медленее). Изначально было 3 блока, но записи переполняются, и начинают делиться. Фактически получается что начинают строиться подуровни.
И эта структура начинает превращаться из 3 уровней, в более многоуровневую структуру.
Начинается работа администратора. Он должен отменить индекс(снять его), и создать его заново. Для этого есть специальные команды. Многие бугалтерские программы делают, чтоб он при загрузке переиндексировался. Иначе теряются индексы, от частых изменений. В SQL серверах это происходит реже, но и там переиндексирование надо делать(переиндексирование –это снять индекс, и создать заново).
Появление дополнительных уровней называется РАЗБАЛАСИРОВКОЙ выше критической глубины (depth).
В SQL сервере, начиная с версии 2005, предусмотрена специальная команда, позволяющая после её запуска от имени администратора, организовать этот современный БАЛАНСИРОВАННЫЙ ИНДЕКС.
§§ 1. Основные правила выбора ТАБЛИЦ при индексировании.
Прим. это м.б. таблицы адресов, городов, районов.
§§ 2. Основные правила выбора СТОЛБЦОВ при создании индексов.
Прим. города – по названию, люди – по годам рождений.
Прим. FoxPro позволяет создавать такие индексы по N начальным символам.
§§ 3. Основные принципы при создании СОСТАВНЫХ индексов (по нескольким полям одновременно).
(Т.е. если столбцы Город и Фамилия кроме самой таблицы есть ещё и в индексе, то при запросе они будут получены из индекса, а не из таблицы.)
§§ 4. Не рекомендуется создавать индексы, включая составные, по столбцам, которые:
(sin значения поля искать нельзя – работать не будет.)
§§ 5. Следует всегда стремиться к уменьшению числа индексов, что сказывается на производительности.
Как правило, индексы создаются для ЗАПРОСОВ (чтобы считывать данные быстрее) и для поддержания ССЫЛОЧНОЙ ЦЕЛОСТНОСТИ (нужен FK). Один индекс может служить одновременно для обеих целей. Если индекс никогда не используется для запросов, то создавать его не следует, а СЦ обеспечить с помощью триггеров. Т.е. можно сделать, но считается дурным тоном, как через дорогу нехорошо переходить, но переходят же люди.
Реализованы пока только в Oracle, т.к. являются достаточно новыми. Специально предназначены для колонок с небольшим числом уникальных значений. Если М и Ж, то 2 значения, хранится маска на все записи, где М и где Ж. Рекомендуется использовать где уникальных значений не более 10. Они занимают в 80% меньше места и работают значительно быстрее. Их нельзя использовать для проверки ссылочной целостности.
Хеш-адресацией или хеш-индексированием называется технология быстрого прямого доступа к хранимой записи на основе значения обычного числового поля.
Всякого рода индексирование, в том числе битовые индексы, предполагают наличие ещё одного файла: для десктоповских СУБД – физического, для SQL-сервера – логического (находящегося в одном физическом). Хеширование не требует дополнительного файла.
Основные принципы хеширования.
(Т.е. берётся какое-то поле, от значения этого поля вычисляется хеш-функция, и это значение используется в качестве адреса, и запись располагается по этому адресу.)
Хоть и для хеширования нет дополнительного файла, но поиск через индексный файл заменяется тем, что процессор считает хеш-функцию. Но в оперативной памяти функция считается достаточно быстро, основная проблема здесь – уникальные значения. Поскольку БД стали сейчас совсем большими, то возникает проблема: при большом количестве значений начинают появляться дубли. Даже для Primary Key трудно найти функцию, которая будет работать с таким объёмом данных. Это привело к тому, что вместо хеш-функции используется b3-дерево, где научились уходить от проблем.
Недостатки:
Их научились обходить.
Одним из способов борьбы с коллизиями является использования значения хеш-функции не в качестве адреса, а в качестве адреса привязки, т.е. некоторой цепочки указателей; внутри цепочки производится потом дополнительный поиск в оперативной памяти. Фактически, для хорошей работы хеширования необходимо сначала рассчитать, какой размер таблицы и значений там будет. Например, перечень городов.
Второй способ – использование расширяемого (или динамического) хеширования: доступ к диску разбивается как бы на 2 части. При этом необходимо, чтобы значения в хеш-поле были уникальными или поле ключевым.
Основные принципы расширяемого хеширования:
Хранимый файл всегда имеет связанный с ним каталог, он состоит из заголовка, содержащего d значений, где d – глубина каталога, соответственно 2d указателей на страницы с несколькими записями на каждой. Таким образом, с помощью d значений можно организовать доступ к 2d страницам. В результате вычисления хеш-функции получается несколько бит псевдокода s, первые d бит рассматриваются как указатель на страницу, остальные используются для поиска записи на странице. Т.о. на одной странице могут появляться эти КОЛЛИЗИИ.
Основные проблемы расширяемого хеширования появляются при добавлении новых записей и особенно тогда, когда страница переполнена, следовательно, d надо менять. Если предусмотреть, что d взято с запасом, то особых проблем не будет.
Как правило, используется в СУБД среднего и большого размера. SQL-сервер – сервер среднего класса, а кластеризация в нем уже есть.
Идея кластеризации заключается в наиболее близком физическом размещении на диске логически связанных между собой данных (например, по какому-нибудь полю, по ключу). Записи физически лежат друг за другом. Особенно хорошо кластеризация работает, когда нужно считывать массивы. Опустили головку на диск, сосчитали подряд нужное число записей, подняли.
Дополнительный индексный файл не нужен. Может быть дополнительно приделан индекс или хеширование для улучшения работы.
2 подхода: внутрифайловая и межфайловая кластеризация. Внутрифайловая – это когда записи располагаются друг за другом в рамках одной таблицы. Межфайловая – друг за другом располагаются записи из связанных таблиц (считывается запись поочерёдно, то из одной, то из другой).
Основные проблемы возникают при добавлении записей: когда появляется запись, которую нужно разместить между записями. Для этого делают ЗАПАС, за который отвечает параметр fillpart, обычно в % бывает 60-80%. Поэтому фактически вначале данные заносятся разряженными. Со временем опять возникает та же проблема. Диспетчер файлов, пока есть свободные места, даже передвигает записи, чтобы вставить нужную новую запись. Приходит время, когда всё пространство заполнено. К кластерам добавляются новые блоки, называемые Экстентами – непрерывные области ~64 страницы, выделяемые на диске.
Если применить ещё и хеширование, что часто используется (совместно), то хешированный кластер требует ещё больше пустого места (свободного пространства) в блоке для обновления данных, поскольку некоторые адреса могут в принципе не использоваться.
Хешированные кластеры.
Поддерживаются в СУБД Oracle, начиная с 7й версии, выпущенной в 90е годы. Используется хеширование для быстрого доступа к первичному ключу.
Рекомендации для использования таких кластеров.
Часто используются, когда приходится выполнять запросы типа: найти поставщиков из города N.
Часто оказываются эффективнее индексов. Файл городов в этом случае оказывается родительским, а файл поставщиков называется дочерним, и структура называется Родительско-Дочерней. Родительский файл (т.е. файл городов) содержит одну хранимую запись для каждого города. Т.е. есть множество городов (Лондон, Бостон…), составляется цепочка всех поставщиков, у которых указан Лондон, и аналогично для остальных городов.
К недостаткам такого рода механизма поиска записей следует отнести желательность кластеризации (когда кластерный индекс – тогда всё хорошо).
Если родительский файл (городов) совсем большой, то для него может понадобиться дополнительное индексирование или хеширование.
Недостатком также является то, что трудно создавать такую структуру, когда записи ещё нет. Т.е. индексирование: индекс сделали и записи добавляются, индекс сам переделывается каждый раз. А вот цепочку указателей обычно делают тогда, когда есть какой-то набор записей.