Дерево на б

Руководство по PostGIS

4.5. Построение индексов

<<< предыдущая глава | оглавление | следующая глава >>>

Индексы делают возможным использование пространственной базы данных для больших наборов данных. Без индексации, любой поиск приводил бы к «последовательному сканированию» каждой записи в базе данных. Индексация организовывает данные в поисковое дерево, по которому можно быстро перемещаться, чтобы быстро найти конкретную запись. PostgreSQL по умолчанию поддерживает три вида индексов: индексы B-Tree, индексы R-Tree и индексы GiST.

  • B-Tree (B-деревья) используются, когда данные могут быть отсортированы вдоль одной оси; например, числа, символы, даты. Данные ГИС не могут быть рациональным способом отсортированы вдоль одной оси (что больше: (0,0) или (0,1) или (1,0)?), а потому для их индексирования B-Tree не помогут.
  • R-Tree ( R-деревья) разбивают данные на прямоугольники, под-прямоугольники, под-под-прямоугольники и т.д. R-Tree используются в некоторых пространственных базах данных для индексации данных ГИС, но в PostgreSQL реализация R-Tree не столь надежна, как реализация GiST.
  • Индексы GiST (Generalized Search Trees — обобщенные деревья поиска) разделяют данные на «объекты по одну сторону » («things to one side»), «пересекающиеся объекты » («things which overlap»), «объекты внутри» («things which are inside») и могут быть использованы для многих типов данных, включая данные ГИС. PostGIS использует реализацию R-Tree поверх GiST для индексации данных ГИС.

4.5.1. Индексы GiST

GiST означает «обобщенное поисковое дерево» («Generalized Search Tree») и является общей формой индексации. Кроме индексации ГИС, GiST используется для ускорения поиска для всех видов нерегулярных структур данных (целочисленные массивы, спектральные данные и т.д.), к которым неприменимо обычное индексирование B-Tree.

Когда таблица данных ГИС вырастает до нескольких тысяч записей, создание индексов необходимо для ускорения поиска пространственных данных (кроме случаев, когда весь ваш поиск основывается атрибутах. Тогда вам достаточно обычных индексов полей атрибутов).

Ниже описан синтаксис запроса для создания GiST-индекса столбца «geometry»:

CREATE INDEX [indexname] ON [tablename] USING GIST ( [geometryfield] );

Создание пространственного индекса требует интенсивных вычислений: для таблицы размером 1 миллион строк на машине Solaris 300MHz создание индекса заняло около 1 часа. После создания индекса важно заставить PostgreSQL собрать табличную статистику, которая используется для оптимизации запросов:

VACUUM ANALYZE [table_name] [column_name]; — Это необходимо только для PostgreSQL 7.4 и более старых SELECT UPDATE_GEOMETRY_STATS([table_name], [column_name]);

В PostgreSQL индексы GiST имеют два преимущества перед R-Tree. Во-первых, индексы GiST являются «null-безопасными» («null safe»). Это означает, что они могут индексировать столбцы, содержащие значения null. Во-вторых, индексы GiST поддерживают концепцию «потерь» («lossiness»), которая имеет значение, когда объекты ГИС занимают больше 8К (размер страницы PostgreSQL). Потери позволяют PostgreSQL сохранять в индексе только «значимую» часть объекта. В случае объектов ГИС, ими являются охваты. R-Tree не может быть создан для объектов ГИС, занимающих больше 8K.

4.5.2. Использование индексов

Как правило, индексы ускоряют доступ к данным оставаясь при этом прозрачными: как только индекс создан, планировщик запросов самостоятельно решает, использовать ли индексную информацию для создания быстрого плана запроса. К сожалению, планировщик запросов в PostgreSQL неоптимально использует индексы GiST. Так, иногда, там, где при поиске должен использоваться пространственный индекс, используется последовательное сканирование всей таблицы выполняемое по умолчанию.

Если вы обнаружили, что ваши пространственные индексы не используются (впрочем, как и индексы атрибутов), есть пара вещей, которые вы можете сделать:

  • Во-первых, убедитесь, что собрана статистика о числе и распределении значений в таблице, для предоставления планировщику запросов лучшей информации при принятии решений об использовании индекса.

    Для PostgreSQL 7.4 и более ранних это делается запуском update_geometry_stats([table_name, column_name]) (подсчет распределения) и VACUUM ANALYZE [table_name] [column_name] (подсчет числа значений). В PostgreSQL 8.0 запуск VACUUM ANALYZE выполнит обе операции. Вам следует регулярно производить вакуумизацию базы данных. Большинство DBA PostgreSQL позволяют регулярно выполнять VACUUM, как задачу cron во время слабой загрузки базы.

  • Если вакуумизация не работает, вы можете заставить планировщик использовать индекс с помощью команды SET ENABLE_SEQSCAN=OFF. Вам следует осторожно использовать эту команду, и только для запросов с пространственными индексами: как правило, планировщик лучше вас знает, когда следует использовать B-Tree. После выполнения запроса, вам следует восстановить прежнее значение , чтобы другие запросы обрабатывались планировщиком как обычно.

    Замечание

    Начиная с версии 0.6 нет необходимости заставлять планировщик использовать индекс с .

  • Если вы считаете, что планировщик неправильно оценивает расходы на последовательное сканирование по сравнению с использованием индекса, можете уменьшить величину random_page_cost в postgresql.conf или использовать SET random_page_cost=#. По умолчанию этот параметр равен 4. Попробуйте установить его в 1 или 2. Уменьшение значения сделает планировщик более склонным к использованию индексов.

<<< предыдущая глава | оглавление | следующая глава >>>

Обсудить в форуме Комментариев — 21

Последнее обновление: May 11 2018

Поделиться

Наверх

Б-деревьяа рис. 4-3 представлено Б-дерево с 3 ключами на узел. Ключи в внутреннем узле окружены указателями или смещениями записей, отсылающими к ключам, которые либо все больше, либо все меньше окруженного ключа. Например, все ключи, меньшие 22, адресуются левой ссылкой, все большие — правой. Для простоты здесь не показаны адреса записей, связанные с каждым ключом.

Рис. 4-3: Б-дерево

В этом двухуровневом дереве мы можем добраться до любого ключа за три доступа к диску. Если бы мы сгруппировали по 100 ключей на узел, то за три доступа к диску мы могли бы найти любой ключ из 1000000. Чтобы сохранить это свойство, нам нужно сохранять сбалансированность дерево во время вставок и удалений. Во время вставки мы исследуем потомка, чтобы определить, можно ли добавить в него узел. Если нет, в дерево добавляется еще один брат, а ключи потомка перераспределяются так, чтобы появилось место для нового узла. Когда мы спускаемся, чтобы вставить ключ, и узел оказывается заполненным, мы рассыпаем корень, у которого появляются новые потомки, так что глубина дерева увеличивается.

Аналогичные действия предпринимаются при удалении — здесь может потребоваться объединить потомков. Этот метод изменения глубины дерева позволяет сохранить сбалансированность дерева.

Б-дерево Б*-дерево Б+-дерево Б++-дерево
данные хранятся в любом узле любом узле только в листьях только в листьях
при вставке — расщепление 1 x 1 –>2 x 1/2 2 x 1 –>3 x 2/3 1 x 1 –>2 x 1/2 3 x 1 –>4 x 3/4
при удалении — слияние 2 x 1/2 –>1 x 1 3 x 2/3 –>2 x 1 2 x 1/2 –>1 x 1 3 x 1/2 –>2 x 3/4

Таблица 4-1: Реализация Б-деревьев

В таблице 4-1 приведены несколько вариантов Б-деревьев. В стандартных Б-деревьях ключи и данные хранятся как во внутренних узлах, так и в листьях (концевых узлах). Если при спуске по дереву во время вставки встречен заполненный узел, его содержимое перераспределяется между братьями. Если братья тоже полны, создается новый узел и половина ключей потомка пересылается в него. Во время удаления наполовину заполненные потомки являются первыми кандидатами на добавление ключей из прилежащих узлов. Если сами прилежащие узлы полны лишь наполовину, они объединяются так, чтобы получился полный узел.

Б*-деревья устроены аналогично, единственное отличие — узлы заполняются на 2/3. Это приводит к лучшему использованию места, занимаемого деревом, и чуть лучшей производительности.

Рис. 4-4: Б+-дерево

На рис. 4-4 представлено Б+-дерево. Все ключи хранятся в листьях, там же хранится и информационная часть узла. Во внутренних узлах хранятся копии ключей — они помогают искать нужный лист. У указателей смысл немножко не такой, как при работе с обычными Б-деревьями. Левый указатель ведет к ключам, которые меньше заданного значения, правый — ключам, которые больше или равны (GE).

Например, к ключам, меньшим 22, ведет левый указатель, а к ключам от 23 и выше ведет правый. Обратите внимание на то, что ключ 22 повторяется в листе, где хранятся соответствующие ему данные. Во время вставки и удаления необходимо аккуратно работать с родительскими узлами. Когда модифицируются первый ключ в листе, дерево проходится от листа к корню. Последний из GE-указателей, найденный при спуске по дереву, и является тем, который потребуется модифицировать, чтобы отразить новое значение ключа. Поскльку все ключи повторяются в листьях, мы можем связать их для последовательного доступа.

Последний метод, Б++-деревья, мое изобретение. Оно устроено аналогично Б+-деревьям, отличается лишь стратегия расщепления/объединения.

Предположим, что в каждом узле могут храниться k ключей, а в корне их может быть 3k. Перед тем, как во время вставки мы спустимся к потому, мы проверяем пуст ли он. Если это так, ключи, находящиеся в потомке и лвух смежных к нему узлах, объединяются и перераспределяются. Если два смежных узла также заполнены, то добавляется узел. Таким образом, мы получаем уже четыре узла, каждый из которых полон на 3/4. Перед тем, как во время удаления спуститься к потомку, мы проверяем, не полон ли он на 1/2. Если это так, ключи потомка и двух смежных узлов объединяются и перераспределяются. Если два смежных узла сами полны наполовину, они сливаются в два узла, каждый из которых полон на 3/4. Мы, таким образом, оказываемся посредине между заполненностью на 1/2 и полной заполненностью, что позволяет нам ожидать равного числа вставок и удалений.

Напомним, что в корневом узле хранятся 3k ключей. Если во время вставки окажется, что корень полон, мы распределяем ключи по четырем новым узлам, каждый из которых полон на 3/4. Это увеличивает высоту дерева. Во время удаления мы исследуем потомков. Если имеется только три потомка и они полны наполовину, переносим их содержимое в корень, в результате чего высота дерева уменьшается.

Другой способ описать работу с деревом — сказать, что мы собираем три узла, а затем рассыпаем их. При вставке, когда нам нужен дополнительный узел, мы рассыпаем на четыре узла. При удалении, когда узел нужно удалить, мы рассыпаем на два узла. Симметрия операций позволяет использовать при реализации вставки и удаления одни и те же собирающие/рассыпающие функции.

Абстрактное бинарное дерево

Лекция Деревья

 

Деревья(trees) используются для представления отношения. Все деревья являются иерархическимипо своей сути. Интуитивное значение этого термина состоит в том, что между узлами дерева существует отношение "родительский-дочерний". Если ребро со­единяет узел n и узел т, причем узел п находится выше узла т, то узел n счи­тается родителем (parent) узла т, а узел т — его дочерним узлом(child) . В де­реве, изображенном на рис. 10.1,узлы В и С являются дочерними по отношению к узлу А. Дочерние узлы, имеющие одного и того же родителя, — например, уз­лы В и С — называются братьями(siblings) . Каждый узел дерева имеет по крайней мере одного родителя, причем в дереве существует только один узел, не имеющий предков. Такой узел называется корнем дерева(root) . На рис. 10.1корнем является узел А. Узел, у которого нет дочерних узлов, называется лис­том дерева(leaf). Листьями дерева, изображенного на рис. 10.1, являются узлы С, D, Е и F.

D E F

Рис. 10.1. Дерево общего в

Отношения между родительским и дочерним узлом с абстрактной точки зре­ния является отношением между предком(ancestor) и потомком(descendant). На рис. 10.1узел А является предком узла Д следовательно, узел D является по­томком узла А. Не все узлы могут быть связаны отношениями "предок-потомок": узлы В и С, например, не связаны родственными отношениями. Однако корень любого дерева является предком каждого его узла. Поддеревом(subtree) называется любой узел дерева со всеми его потомками. Поддеревом узлап является поддерево, корнем которого является узел n. Например, на рис. 10.2 показано поддерево дерева, изображенного на рис. 10.1. Корнем этого поддерева является узел В, а само поддерево является поддеревом узла А.

С формальной точки зрения, дерево общего вида(general tree) T представляет собой множество, состоящее из одного или нескольких узлов, принадлежащих непересекающимся подмножествам, указанным ниже.

• Отдельный узел r, корень.

• Множество поддеревьев корня r.

Бинарное дерево(binary tree) — это множество узлов Т, таких что

• множество Т пусто, или

• множество Т распадается на три непересекающихся подмножества:

• отдельный корень r, корень;

• два возможно пустых поддерева бинарного дерева, которые называются левым и правым поддеревьями(leaf and right subtrees) корня r, соответственно.

 

 

В качестве иллюстрации использования бинарных деревьев для представле­ния данных в иерархическом виде рассмотрим рис.

10.4. На этом рисунке би­нарные деревья представляют алгебраические выражения, содержащие бинарные операторы +, -, * и /. Для представления выражения а-b оператор помещается в корневой узел, а операнды а и b— в его левый и правый дочерние узлы, соответственно (рис. 10.4). На рис. 10.4, б представлено выражение a-b/с, где поддерево представляет подвыражение b/с. Аналогичная ситуация показана на рис. 10.4, в, где изображено выражение (а-b)*с. В узлах этих деревьев хранятся операнды выражений, а в остальных узлах — операторы. Скобки в этих деревьях не представлены. Бинарное дерево создает иерархию операций, т.е. дерево однозначно определяет порядок вычисления выражения.

б) в)

Рис. 10.4. Бинарные деревья, представляющие алгебраические выражения

Бинарное дерево поиска— это бинарное дерево, некоторым образом упорядоченное в соответ­ствии со значениями, содержащимися в его узлах. Каждый узел п бинарного де­рева поиска обладает следующими тремя свойствами:

• Значение узла п больше всех значений, содержащихся в левом поддереве TL.

• Значение узла п меньше всех значений, содержащихся в правом поддереве ТR.

• Деревья TL и ТR являются деревьями бинарного поиска.

На рис. 10.5 показан пример бинарного дерева поиска. Как следует из его назва­ния, это дерево обеспечивает возможности поиска конкретного элемента. Позд­нее мы рассмотрим эту структуру данных более подробно.

 

Высота деревьев. Деревья могут иметь разную форму. Например, хотя деревья, изображенные на рис. 10.6, состоят из одинаковых узлов, они имеют совершенно разную структуру. Каждое из этих деревьев содержит семь узлов, но некоторые деревья "выше" других. Высота (height) дерева — это количество узлов, располо­женных на самом длинном пути от корня к листу. Например, высота деревьев, по­казанных на рис. 10.6, равна 3, 5 и 7, соответственно. Интуитивное представление о высоте деревьев может привести к заключению, что их высота равна 2, 4 и 6, соответственно. Действительно, многие авторы используют именно интуитивное оп­ределение высоты дерева (подсчитывая количество ребер на самом длинном пути от корня до дерева. — Прим. ред.). Однако принятое нами определение позволяет более четко формулировать многие алгоритмы и свойства деревьев.

 

Полное, совершенное и сбалансированное дерево.В полном бинарном дереве(full binary tree), имеющем высоту h, все узлы, расположенные на уровнях, меньших уровня h, имеют по два дочерних узла. На рис. 10.7 представлено пол­ное бинарное дерево, имеющее высоту, равную 3. Каждый узел полного бинарно­го дерева имеет левое и правое поддерево, имеющие одинаковую высоту. Среди всех бинарных деревьев, высота которых равна h, полное бинарное дерево имеет максимально возможное количество листьев, и все они расположены на уровне h. Проще говоря, в полном бинарном дереве нет пропущенных узлов.

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

• Если дерево Т пусто, то оно является полным бинарным деревом, имеющим

высоту, равную 0.

• Если дерево T не пусто, и его высота равна h > 0, то дерево T является полным бинарным деревом, если поддеревья его корня являются полными бинарными деревьями, имеющими высоту h-1.

Это определение хорошо отражает рекурсивную природу бинарного дерева.

Совершенное бинарное дерево(complete binary tree), имеющее высоту h, — это бинарное дерево, которое является полным вплоть до уровня h-1, а уровень h заполнен слева направо так, как показано на рис. 10.8.

Рис. 10.8. Совершенное бинарное дерево

Очевидно, что полное бинарное дерево является совершенным.

Бинарное дерево называется сбалансированным по высоте(height balanced), или просто сбалансированным(balanced), если высота правого поддерева любого его узла отличается от высоты левого поддерева не больше, чем на 1. Бинарные деревья, изображенные на рис. 10.8и 10.6, а, яв­ляются сбалансированными, а деревья, представленные на рис. 10.6, б и 10.6, в — нет. Совершенное бинарное дерево является сбалансированным. Итак, повторим кратко введенные понятия.

Абстрактное бинарное дерево

B бинарном дереве существует несколько способов обхода. Стандартными являются три порядка обхода дерева: прямой, симметричный и обратный. Все они описываются в следующем разделе. Над абстрактным бинарным деревом выполняются следующие операции.

12


Дата добавления: 2016-01-20; просмотров: 1014;


ПОСМОТРЕТЬ ЕЩЕ:

Добавить комментарий

Закрыть меню