Программирование баз данных MS SQL Server (1084479), страница 86
Текст из файла (страница 86)
Если количество данных, доступ к которым осуществляется с помощью индекса, невелико, то найти непосредственное указание на действительное местонахождение искомых данных можно сразу же с помощью корневого узла. В таком случае в конечном итоге формируется структура, которая выглядит так, как показано на рис. 9. Е Рис. 9.1. Структур индекса, соппоятего из одного коугневого узла Итак, поиск в индексе начинается с корневого узла, после чего осуществляется просмотр строк в этом узле до тех пор, пока не обнаруживается указатель на последнюю страницу, которая начинается со значения меньше искомого.
Затем происходит выборка указателя на узел, содержащий сведения об этой странице, и просмотр ее до тех пор, пока не обнаружится требуемая строка. Но в большинстве ситуаций количество данных в столбце, поиск в котором осуществляется с помощью индексов, слишком велико для того, чтобы можно было поместить все указатели на эти данные в корневой узел, поэтому корневой узел применяется для хранения указателей на промежуточные узлы, или так называемые узлы уровня, отличного от листового. Узлы уровня, отличного от листового, представляют собой узлы, находящиеся на одном из уровней между корнем и тем узлом, который позволяет узнать, где физически хранятся данные.
В свою очередь, узлы уровня, отличного от листового, могут указывать либо на узлы другого уровня, отличного от листового, либо на узлы листового уровня (в этом состоит последний обещанный аналог с деревом, поскольку дерево оканчивается листьями). Узлы листового уровня представляют собой узлы, позволяющие получить реальную ссылку на фактические физические данные. Во многом аналогично тому, что процесс перемещения по ветвям дерева оканчивается достижением отдельного листа, процесс продвижения по индексу оканчивается достижением узла листового уровня, а от этого узла индекса мы можем непосредственно перейти к узлу с данными, в котором хранятся действительные искомые данные.
Структуры памяти и индексные структуры БЯ1. Бегчег 341 то вместо указания на то, что происходит разбиение узла, принято применять термин разбиение страницы. Процесс разбиения страницы показан на рис. 9.3. етес. 9З. еероцессразбиения страницы При каждом разбиении страницы автоматически происходит переиецение данных для обеспечюшя поддержки сбалансированности дерева. Первая посавина данных остается на старой странице, а остолънъм даннъм переносятся на новую страницу.
Таким образам, разбиение осуисествляется пРимерно наполовину и деРево остается сбалансированным. Даже краткие размышления по поводу того, как происходит процесс разбиения, позволяют понять, что во время разбиения возникают значительные издержки. Дело в том, что в процессе разбиения не происходит лишь вставка одной страницы, а выполняются следующие действия: П создание новой страницы; С3 перенос части строк с существующей страницы на новую страницу; ъе добавление новой строки к одной из страниц; О добавление еще одной строки в родительский узел. Но на этом работа не заканчивается.
Поскольку узлы образуют древовидную структуру, создается возможность своего рода каскадных действий. После того как создается новая страница (в результате разбиения), возникает необходимость ввести еще одну строку в родительский узел. Появление новой строки в родительском узле также может привести к возникновению необходимости осуществить разбиение страницы, но уже на уровне родительских узлов, поэтому процесс разбиения возобновляется на 342 Глава 9 более высоком уровне. В действительности такая последовательность операций может продолжаться, охватывая все более и более высокие уровни, и в конечном итоге может даже затронуть корневой узел.
Если происходит разбиение корневого узла, то фактически в связи с этим создаются две дополнительные страницы. Но поскольку количество корневых узлов не может быть больше единицы, то страница, на которой перед этим находились строки корневого узла, разбивается на две страницы, а уровень, на котором она находится, становится новым промежуточным уровнем дерева. После этого создается совершенно новый корневой узел, в котором содержатся две строки (одна из них относится к старому корневому узлу, а вторая — к странице, полученной в результате разбиения). Вполне очевидно, что выполняемые каскадно операции разбиения страниц могут оказывать весьма негативное влияние на производительность системы. Характерным признаком того, что происходит каскадное разбиение, является ситуация, в которой создается впечатление, что процессы обработки данных на сервере кажутся приостановившимися на несколько секунд (на то время, когда происходит разбиение и перезапись страниц).
Информация о том, как предотвратить возникновение ситуаций разбиения страниц, приведена в конце данной главы. Безусловно, опефа уии разбиения стфа ниц на листовом уфовне пфои сходят очень часто, но тазсие оиефауии в узлах ифомежуточных уфовней пфошходят гораздо феже. Помере увеличения размеров таблицы операции разбиения стфаниу осуществляются на каждом уфовнеиндекса, но е узлах промежуточных уровней имеется только по одной строке в фасчете на несколько сп фок узла более низкого уровня поэтому количество страниц, подвергаемых разбиению, становится все меньше и меньше по мере дальнейшего продвижения вверх по дефеву. К тому же разбиение на уровне выше листового может иметь место лишь в том случае, если ифтсзошло фазбиение на более низном уфовне.
Это означоезд что операции фазбиения страни у. осуществляемые на более высоких уфовнях дефева, по своему характеру являются кумулятивными, т.е. возникающими в результате осуществления ряда подобных операций (и поэтому их выполнение связано с определенным снижением производительности). В СУБД ЯО) Яеггег предусмотрен целый ряд различных типов индексов (информация об этом будет вскоре приведена), но в индексах всех этих типов в той или иной форме используется подход, основанный на применении В-деревьев. На самом деле все эти индексы весьма напоминают друг друга по своей структуре и вместе с тем обладают заметными отличительными особенностями, поскольку В-деревья позволяют реализовывать исключительно разнообразные требования.
Однако, как будет описано ниже, некоторые различия между индексами разных типов действительно являются весьма существенными. Кроме того, от типа применяемого индекса во многом зависит производительность системы. Следует отметить, что в индексах Бас. Ьгззяг узлы дерева ифедппавленсч в форме стфаниу, а сами индексы имеют дфевовидную стфуктуфу, копизфоя включагт корневой узел, узлы уровню, отличных от листового, и узлы листового уровня. Но подобный принцип афганизации данных может применяться не только в 5(~® Безпгт, но и в дфугих баз х данных и даже в системах пфедставления данных, отличных от баз данных. Структуры памяти н индексные структуры БЯЕ Яегчег 343 Принципы организации доступа к данным а СУБД 8® Берег Вообще говоря, в СУБД ЯЯь Яегчег применяются только два указанных ниже способа выборки запрашиваемых данных.
«2 Выборка данных п)тем полного просмотра таблицы. «:з Выборка данных с помощью индекса. Метод выборки данных, применяемый в СУБД ЯОЕ Бегчег для выполнения конкретного запроса, зависит от состава доступных индексов, от того, в каких столбцах находятся требуемые данные, какого рода соединения выполняются и какие размеры имеют таблицы. Использование полного просмотра таблицы Процесс полного просмотра таблицы является довольно несложным. При осуществлении полного просмотра таблицы СУБД зать Яегчег начинает свою работу с физического начала таблицы, после чего считывает каждую строку таблицы. После обнаружения строк, соответствующих критериям запроса, СУБД включает эти строки в результирующий набор.
Широко распространено такое мнение, что операции выборки данных с помощью полного просмотра таблицы характеризуются существенными недостатками. Такое мнение соответствует действительности. Тем не менее операции с полным просмотром таблицы могут фактически оказаться в некоторых обстоятельствах самым быстрым методом доступа.
Как правило, именно это происходит при выборке данных из относительно небольших таблиц. Точные данные о размерах таблицы, при которых способ выборки данных с полным просмотром становится наиболее быстродействующим, в основном зависят от размеров строк таблицы и от характерных особенностей самого запроса. Попьопайтесь сами огфеделить, почему тфименение опфатфа НХ1ЯТН в нонстфукции ННННН запУгоса оказывает такое влияние на пузтгзводипмльность фи пфеходе от одного способа выйфки и д)зугому Дело в том, что при использовании опфотофа ЯХ1НТБ поиск данных в СУБД ба батист гфекУзащ естся фазу после обнаружения хотя бы одной сгфоки, со. ответствующей ~фитфием поиска.
Если ведется офаботха таблицьь состатцсй из миллиона сгфок, и ст)гона, соответствующая к)пстфиям, обнафухсивается на т9егльем месте, то использование опции НХ1НТН позволяет исключить необходимость чтения 999 997 софок! Опция «чОТ НХ1НТН действует в основном по такому же пУпгнципу Использование индексов Если планировщик запросов зЯз. Яегчег принимает решение об использовании индексов, то процесс выборки данных осуществляется фактически во многом аналогично тому, как происходит полный просмотр таблицы, с учетом определенных способов сокращения.
В процессе оптимизации запроса программа-оптимизатор просматривает все доступные индексы и выбирает из них наилучший (при этом в основном используется информация, заданная в операциях соединения и в конструкции «ЕНЕНЕ, в сочетании со статистической информацией об устройстве индекса, которая ведется в СУБД $«11. Яегчег). После выбора применяемого индекса СУБД ЯЯЕ Яегчег переходит по древовидной структуре к тому узлу индекса, который указывает на данные, соответствую- 344 Глава 9 щие установленным критериям.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
