Волк В.К. Базы данных. Практикум по проектированию, программированию и администрированию баз данных, включающий примеры и практические задания для самостоятельного выполнения
 Скачать 3.17 Mb.
|
12.1. Линейный индекс Естественным способом снижения стоимости выборки данных из кучи является отказ от технологии последовательного сканирования и применение методов прямого доступа, предусматривающих наличие специальных указате- лей (адресных ссылок) на строки таблиц, соответствующие критерию выборки. Применение таких методов требует наличия служебных структур данных (ин- дексов), формируемых для основных таблиц базы данных. Простейшей индексной структурой является линейный индекс, представ- ляющий собой классический двунаправленный список, реализованный в виде бинарной таблицы, один из столбцов которой содержит все значения индекси- руемого поля (называемого «ключом индекса»), а второй — указатели на соот- ветствующие строки индексируемой таблицы. Отметим основные особенности устройства индексов: 1) если актуальна задача ускорения поиска по нескольким полям таблицы (ключам), то для одной таблицы может потребоваться несколько индексов — по одному для каждого поискового ключа; 2) мощность (количество строк) индексной таблицы соизмерима с мощ- ностью основной (индексируемой) таблицы базы данных, а в предельном слу- чае обе эти таблицы имеют одинаковую мощность; 3) физический размер индексной таблицы существенно (возможно, в сот- ни раз) меньше размера основной индексируемой таблицы, соответственно ин- декс занимает существенно меньше файловых страниц по сравнению с индек- сируемой таблицей; 4) строки индексной таблицы отсортированы по значению ключа индекса, что позволяет существенно ускорить поиск указателя по значению ключа непо- средственно в самой индексной странице, применяя, например, метод дихото- мии; 5) если индексируемое поле таблицы не является уникальным, одинако- вые его значения могут многократно встречаться в различных строках таблицы и, как следствие, могут оказаться в нескольких файловых страницах. В этом случае поле ключа индекса в индексной таблице будет содержать множества значений-дубликатов, причем пара значений «ключ — ссылка» будет оставать- ся уникальной в пределах всей индексной таблицы; 6) индексные страницы не хранятся в структуре типа кучи — все страни- цы одного индекса организованы (логически) в линейный список (в порядке возрастания или убывания значения ключа индекса), реализуемый с помощью специальных указателей, присутствующих в заголовках всех индексных стра- ниц; 7) операции вставки/удаления строк таблицы, а также операции модифи- кации индексированных столбцов требуют оперативной перестройки соответ- ствующих индексов этой таблицы, что может негативно сказаться на показате- лях производительности. 5 / 19 158 Ниже приведено пошаговое описание алгоритма поиска строк таблицы по значению линейно-индексированного столбца в структуре данных типа куча. Этот алгоритм актуален как для случая индексирования таблицы по уникаль- ному ключу, так и для случая, когда значение индексируемого столбца много- кратно дублируется в разных строках таблицы. – Последовательная загрузка всех индексных страниц (начиная с первой и далее до последней по указателям на следующий элемент списка), в каждой из которых: • выполняется циклическая процедура сравнения значений ключей индек- са с критерием отбора; при их совпадении формируется массив указателей на страницы и строки таблицы; – последовательная загрузка страниц кучи, номера которых попали в мас- сив указателей, в каждой из которых: • выбираются строки таблицы в соответствии с массивом указателей; • формируется результирующая выборка. Пример Размер файловой страницы — 8 kb (2 13 b) Индексируемая таблица базы данных: мощность — около 16 млн (2 24 ) строк; средняя длина одной строки — 2 k; длина индексируемого поля — 8 b; всего строк таблицы в одной странице — 4; всего страниц, занятых таблицей, — около 4 млн (2 24 /2 2 ). Индексная таблица: мощность — около 16 млн (2 24 ) строк; длина строки — 16 b (ключ индекса 8 b + указатель 8 b); строк индекса в одной индексной странице — 512 (2 13 /2 4 ); всего индексных страниц — порядка 32 тыс. (2 24 /2 9 ). Сравним два рассмотренных выше метода поиска данных в куче по кри- терию стоимости реализации простого SQL-запроса: Select * From T1 Where T1.Col = const, где T1 — таблица из рассмотренного выше примера; const — произвольное числовое значение. В модели стоимости будем учитывать только операции доступа к внеш- ней памяти для загрузки файловых страниц. Метод полного прямого сканирования дает оценку стоимости в четыре миллиона единиц, независимо от степени селективности запроса Sel, равной ко- личеству строк таблицы, в которых T1.Col = const. Метод доступа с использованием линейного индекса потребует последо- вательной загрузки некоторого количества K I индексных страниц до тех пор, пока значение ключа индекса не выйдет за пределы диапазона поиска, и до- полнительной загрузки тех K T страниц индексированной таблицы T1, ссылки на которые были найдены (Ind.Col = const) при обработке индексных страниц. Количество K T (Sel) таких «дополнительных» страниц зависит от степени се- 6 / 19 159 лективности запроса Sel, а общая оценка стоимости для этого метода составит K I + K T (Sel). Пессимистическая оценка количества загружаемых индексных страниц K I = 32 768 (когда совпадение будет найдено только в последней из них), опти- мистическая оценка K I = 1, а усредненная оценка K I ≅ 16 000. Пессимистическая оценка количества загружаемых страниц индексируе- мой таблицы K T ≅ 4 000 000, что соответствует ситуации, когда в таблице T1 до- статочно много (больше, чем страниц в куче) одинаковых и равных const зна- чений столбца Col, и при этом они равномерно распределены по всем файловым страницам этой таблицы. Ясно, что вероятность второго пессимистичного случая крайне мала, а вероятность одновременного проявления двух рассмотренных выше пессими- стичных ситуаций равна нулю (что в целом должно нам добавить оптимизма в оценке эффективности линейных индексов). Завершая краткий обзор линейных индексных структур, следует отме- тить, что линейные индексы не нашли практического применения в системах управления реляционными базами данных по причине своей низкой эффектив- ности. В рассмотренном примере усредненная оценка количества операций чте- ния индексных страниц, необходимого для выборки данных из таблицы мощ- ностью в 16 млн строк, составила 16 тыс. единиц. Это, конечно, существенно лучше, чем оценка в 4 млн единиц для метода полного сканирования, но все- таки весьма посредственно по сравнению с многоуровневыми индексными структурами, построенными на базе сбалансированных деревьев. 12.2. Многоуровневый иерархический индекс Основная причина низкой эффективности линейного индекса заключает- ся в его «линейности». Обеспечив возможность прямого (адресного) доступа к файловым страницам кучи, сам индекс остался классической структурой после- довательного доступа к данным — линейным списком, на котором, как извест- но, заданы два основных «поисковых» метода: переход к следующему и пере- ход к предыдущему элементам списка. В отличие от линейных индексов, иерархические (древовидные) структу- ры данных обеспечивают прямой доступ не только к страницам кучи, но и к са- мим индексным страницам, организованным на каждом уровне индекса в по- следовательную списковую структуру. Порядком индекса (P) будем называть количество строк индекса, поме- щающихся в одной индексной странице. Для нашего примера P = 512 (2 9 ), и при этом весь линейный индекс занимает 32 768 (2 15 ) файловых страниц. Рассмотрим процесс построения многоуровневого иерархического индек- са на базе существующего линейного индекса, который теперь будем считать конечным («листовым») уровнем многоуровневого индекса. Все индексные страницы и все строки внутри индексных страниц упорядо- чены по значению ключа индекса, и каждая индексная строка листового уровня 7 / 19 160 содержит указатель на соответствующую строку таблицы базы данных, включа- ющий номер файловой страницы из кучи и номер строки этой страницы. Построим еще один уровень иерархического индекса — линейный ин- декс, страницы которого будут содержать указатели на индексные страницы листового уровня. Потребуются 64 индексных страницы для этого «предлисто- вого» уровня (2 15 /2 9 ), так как каждая индексная страница может содержать P = 512 (2 9 ) ссылок на страницы листового уровня, а всего на листовом уровне 32 768 (2 15 ) страниц. Продолжим построение многоуровневого индекса — создадим еще один уровень, страницы которого будут содержать указатели на индексные страницы предлистового уровня. Здесь нам будет достаточно одной индексной страницы (с восьмикратным запасом, так как указателей надо всего 64, а порядок индекса P = 512). Эта страница называется «корневой страницей» многоуровневого ин- декса или, более кратко, «корнем дерева». В результате построен многоуровневый индекс, страницы которого на каждом уровне связаны в двунаправленные списки, а переходы от страниц верхних (родительских) уровней на страницы нижних (дочерних) уровней вы- полняются по прямым ссылкам в соответствии со значениями ключей индекса. Построенный индекс содержит 32 833 страницы (1 + 64 + 32768), распределен- ные по трем уровням индекса. Количество уровней индекса (H) называют «глубиной индекса», которая зависит от количества страниц кучи N и порядка индекса P: H = Log P (N) + 1. Для нашего примера H = Log 512 (32768) + 1 ≅ 2,665 3. Уровни индекса принято последовательно нумеровать в порядке возрас- тания, начиная от корневого (Level = 0) и заканчивая листовым (Level = H – 1) уровнем. На корневом (нулевом) уровне индекса всегда находится единствен- ная индексная страница N[0] = 1, а количество страниц N[i] на каждом дочернем уровне зависит от количества значений ключа индекса на всех страницах роди- тельского уровня и, в частности, от степени заполнения индексных страниц. Максимально возможное количество страниц на i-м 7 уровне индекса (при 100%-ном заполнении всех индексных страниц) N[i] = P i Ниже приведено описание алгоритма реализации метода поиска строки в куче по значению индексированного столбца, включающего «спуск» от корня индекса до листового уровня с последующей загрузкой страниц кучи, указатели на которые были получены на листовом уровне индекса (рис. 4.8): – получение адреса корневой страницы индекса запросом к системному каталогу базы данных (адрес страницы = file_ID.page_Num); – загрузка корневой индексной страницы, поиск индексной строки, удо- влетворяющей критерию отбора по ключу индекса, определение адреса ин- дексной страницы нижележащего уровня индекса; – загрузка индексной страницы промежуточного уровня индекса; 7 В системе MS SQL-Server принята иная нумерация уровней индекса: нулевым считается листовой уровень, а корневой уровень индекса имеет наибольший номер. 8 / 19 161 – поиск индексной строки, удовлетворяющей критерию отбора по ключу индекса, определение адреса индексной страницы нижележащего уровня; – и т. д. по всем промежуточным уровням индекса; – загрузка индексной строки листового уровня: • выполнение циклической процедуры сравнения значений ключей ин- декса с критерием отбора и формирование массива указателей на строки табли- цы в куче (указатель на строку = file_ID.page_Num.slot_Num); • последовательная загрузка в оперативную память страниц кучи, номера которых попали в массив указателей; • в каждой из загруженных страниц: выборка строк таблицы в соответ- ствии с массивом указателей; • формирование результирующей выборки. Рис. 4.8 Схема доступа к данным типа куча методом спуска по многоуровневому индексу Как видно из рисунка 4.8 и приведенного выше описания алгоритма «спуска по дереву», для получения ссылки на страницу кучи, содержащую уни- кальное значение искомого ключа, потребуется загрузка одной индексной стра- ницы на каждом уровне индекса (в нашем примере H = 3) и дополнительно за- 9 / 19 162 грузка одной страницы кучи. Общая оценка стоимости запроса в этом случае составит 4 единицы (сравните с оценкой 16 000 единиц для линейного индекса). Если многоуровневый индекс построен по неуникальному столбцу таб- лицы, его преимущество по сравнению с линейным индексом будет не настоль- ко радикальным: потребуется загрузка одной индексной страницы на каждом нелистовом уровне индекса (в нашем примере 2 страницы) и дополнительно за- грузка K I страниц листового уровня индекса, количество которых зависит от степени селективности запроса Sel и порядка индекса P: K I = Sel/P. Если, например, P = 512 (как в нашем примере), а степень селективности пре- диката выборки по индексируемому ключу составляет 2%, то при мощности табли- цы в 16 млн строк получим значение оценки стоимости K I = 320000/512 ≅ 640, что существенно меньше 16 000 единиц для линейного индекса. 12.3. Кластеризованный уникальный индекс Рассмотренный выше многоуровневый индекс — автономный объект ба- зы данных, существующий отдельно от структуры кучи, на базе которой он был создан. Такие индексы (в терминологии MS SQL-Server) принято называть «не- кластеризованными» (nonclustered), подчеркивая тот факт, что данные индекси- рованной таблицы и индексы, связанные с этой таблицей, хранятся отдельно друг от друга, то есть в разных «кластерах». Некластеризованные индексы существенно ускоряют поиск данных по уникальным ключам, но при высокой степени селективности предиката выбор- ки их эффективность резко падает. Некластеризованные индексы хорошо работают в запросах с точечными условиями выборки (Select … Where Col = Const) и гораздо хуже, если условие выборки содержит диапазон значений ключевого поля (Select…Where Col Between Const1 And Const2). Некластеризованные индексы недостаточно эффективны при выполнении запросов, требующих соединения таблиц или группировки их строк, реализация которых основана на алгоритмах сортировки и слияния данных. Кластеризованный (clustered) индекс — это структура данных, объединя- ющая в единый «кластер» и строки индексируемой таблицы, и собственно ин- декс. В кластеризованном индексе файловые страницы, содержащие строки ин- дексируемой таблицы, перестают быть кучей — они упорядочиваются по зна- чению ключа (как внутри страниц, так и между страницами) и в таком виде за- нимают место листового уровня многоуровневого индекса, страницы которого образуют двунаправленный список, обеспечивающий возможность быстрого перехода на последующую или предыдущую страницу. Остальные (верхние) уровни кластеризованного индекса устроены так же, как и в некластеризован- ных индексах (рис. 4.9). Так как данные таблиц в кластеризованном индексе хранятся в уже упо- рядоченном виде, такие индексы оказываются эффективными в запросах с диа- пазонными условиями выборки, а также при реализации методов, требующих сортировки данных. 10 / 19 163 Рис. 4.9 Схема доступа к данным типа кластеризованный многоуровневый индекс Физическая упорядоченность строк таблицы в кластеризованном индексе накладывает существенное ограничение на его использование: в одной таблице может быть создано не более одного такого индекса. Как правило, кластеризо- ванный индекс создается по одному из уникальных столбцов таблицы, а при наличии в таблице первичного ключа сервер автоматически (по умолчанию) со- здает по нему кластеризованный индекс. Если кластеризованный индекс создается до заполнения таблицы, то при последующей вставке строк они сразу упорядочиваются по значению ключа индекса, формируя листовой уровень индекса как двусвязный список файловых страниц. Если кластеризованный индекс создается на базе уже заполненной табли- цы, сервер автоматически перестраивает кучу в список листового уровня ин- декса и затем достраивает все остальные его уровни, вплоть до корневого. Если к этому моменту в таблице уже существовали некластеризованные индексы, то все они будут автоматически перестроены, так как в этом случае изменяется формат указателя листового уровня некластеризованного индекса: 11 / 19 164 вместо ссылки на строку таблицы (номер слота файловой страницы) этот указа- тель теперь будет содержать значение ключа кластеризованного индекса, соот- ветствующего этой строке (которое однозначно определяет номер слота). Такой подход несущественно увеличивает стоимость поиска по значению ключа индекса, так как требует дополнительного «спуска» по кластеризован- ному индексу, однако он дает существенную экономию при реализации проце- дур реиндексации — перестройки индексов таблицы после модификации ее данных в условиях, когда в таблице, кроме кластеризованного индекса, создано большое количество некластеризованных индексов. Если в таблице модифицируется значение неиндексированного столбца и это приводит к перераспределению данных между страницами кластеризован- ного индекса, то это никак не скажется на некластеризованных индексах, так как в них отсутствуют указатели на физическое размещение страниц. Если же в аналогичной ситуации изменение коснулось одного из индексированных столбцов, то это потребует перестройки только этого индекса. 12.4. Фактор заполнения индексных станиц Как было показано выше, порядок индекса P, определяющий количество индексных строк на одной индексной странице, влияет на глубину индекса H = Log P (N) + 1 и, следовательно, на стоимость алгоритма спуска от корневого до листового уровня индекса. Если оптимизировать индексные структуры по критерию производитель- ности выполнения операций поиска данных, следует стремиться к увеличению порядка индекса P как за счет минимизации длины индексных записей (ключ + ссылка), так и за счет максимального использования пространства ин- дексных страниц, то есть 100%-ного заполнения этих страниц индексными за- писями. Однако, 100%-ное заполнение индексных страниц приведет к резкому снижению производительности выполнения операций модификации данных, так как вставка и удаление строк таблицы потребуют оперативной перестрой- ки всех ее индексов, связанной с массовым проведением весьма дорогостоя- щих операций расщепления и слияния индексных страниц на всех уровнях индексов. В этих условиях администратор базы данных, учитывая специфику струк- туры базы данных, характер типовых запросов и результаты мониторинга рабо- ты пользователей, может принять компромиссное решение и установить тре- буемое значение фактора заполнения индексных страниц в процентах от зна- чения порядка индекса P (например, 20% при интенсивном выполнении опера- ций модификации данных и 80% — в противном случае). Сервер баз данных будет учитывать установленное значение фактора за- полнения при начальном формировании индексов, то есть, фактически, будет занижать допустимый порядок индекса, что приведет к увеличению глубины индекса и, как следствие, к снижению производительности выполнения опера- ций выборки данных. 12 / 19 165 В процессе эксплуатации базы данных реальное значение фактора запол- нения будет изменяться (вспомним про расщепление и слияние страниц при вставке и удалении строк таблицы), однако при каждом выполнении операции реиндексации сервер автоматически перестроит индексы в соответствии с уста- новленным начальным значением фактора заполнения. По умолчанию сервер устанавливает фактор заполнения индексных стра- ниц на уровне 50%. 12.5. Рекомендации по использованию индексов Прежде, чем принимать решение об индексировании таблиц, следует провести детальный анализ и попытаться понять, индексирование каких их столбцов позволит повысить производительность работы базы данных. Для этого рекомендуется проанализировать активность пользователей, собрать и обработать статистику выполняемых запросов к базе данных, обращая внима- ние на интенсивность выполнения поисковых и модифицирующих запросов, наборы соединяемых в запросах таблиц, критерии поиска данных в таблицах, условия группировки и сортировки данных и т. д. Кластеризованные индексы – По умолчанию сервер автоматически создаст кластеризованный индекс для первичного ключа таблицы, и с таким его решением следует согласиться в подавляющем большинстве случаев; – если создается подчиненная таблица, будет полезно создать кластеризо- ванный индекс для составного ключа, включающего пару «первичный ключ — внешний ключ», так как в процессе эксплуатации базы данных, как правило, часто будут выполняться запросы с эквисоединением таблиц, требующие сор- тировки данных; – если планируется создать единственный индекс в таблице, пусть он бу- дет кластеризованным; – если не планируется создавать в таблице первичный ключ (и такое тоже случается), следует создать кластеризованный индекс по столбцу, который ча- сто используется в условиях группировки и операторах сравнения between, >, >=, <= или < ; – не рекомендуется создавать кластеризованные индексы для столбцов с «длинными» типами данных: во-первых, это приведет к уменьшению порядка самого этого индекса и, как следствие, к увеличению его глубины, а во-вторых, что гораздо важнее, этот «длинный тип» будет многократно дублироваться в качестве конечной ссылки на страницах листовых уровней всех некластеризо- ванных индексов этой таблицы, что также негативно скажется на их структуре. Некластеризованные индексы – Некластеризованные индексы целесообразно создавать для тех столб- цов таблицы, которые участвуют в SQL-запросах в разделах Where, Having, Group BY, а также в условиях соединения таблиц Join; 13 / 19 166 – не следует применять такие индексы для часто изменяемых столбцов таблиц: ускорение поиска данных станет незаметным на фоне существенных временных потерь на реиндексацию после каждого такого изменения; – не следует также применять некластеризованные индексы для таблиц малой мощности: при небольшом количестве файловых страниц метод полного сканирования кучи может оказаться более эффективным по сравнению с мето- дами поиска по ключу индекса; – наибольший эффект от применения некластеризованного индекса до- стигается, когда индексируемый столбец содержит относительно много различ- ных (уникальных) значений, а также при небольшой степени селективности предиката выборки (т. е. когда количество строк, соответствующих критерию отбора по ключу индекса, значительно меньше общего количества строк в таб- лице). Серверы баз данных поддерживают различные специальные типы индек- сов, например композитные индексы или индексы с включаемыми неиндексиру- емыми столбцами, позволяющие повысить производительность выполнения запросов определенных типов. Структуры некоторых из таких индексов пред- стоит исследовать при выполнении заданий практикума по администрированию (глава 14). 14 / 19 |