2011-05-13 Пилим GiST

Пиля K-D-B-дерево для GiST'а в PostgreSQL, потихоньку его вкуриваю… Интересные вещи о нём:

• В 9.1 (сейчас бета), как я уже написал, есть поддержка поиска ближайших соседей, то есть просмотра дерева поиска в порядке возрастания удалённости от искомого элемента.
• Один из двух авторов — тот самый «индеец», Олег Бартунов.
• Размер страницы индекса в постгресе — обычно 8 Кб.
• Чтобы реализовать канонiчное KDB-дерево, а точнее — любое дерево поиска, в котором следующее разбиение пространства зависит от предыдущего, GiST нужно допилить (конкретно функцию gistinserttuples), чтобы picksplit’у передавался родительский узел, потому что в оригинале ему только передаётся список самих элементов, которые нужно разбить на две группы. Вот я щас как раз это допиливаю.
• Предикаты на нелистовых страницах модифицируются не после вставки элемента в листовую страницу, а до! Оно сразу, когда ищет, куда бы вставить элемент, сначала дёргает по всем элементам страницы penalty, выбирает элемент с минимальным, потом вычисляет union предиката и нового вставляемого элемента (O_o), и сохраняет, если в итоге получается другой предикат. Чуть-чуть не совсем логичная схема, если в вашем индексе внутренние и листовые узлы хранят разные типы ключей, но реализацию упрощает. Разные типы — то есть не как в R-дереве — в листах квадратики и во внутренних квадратики, а как например в KDB — в листах N-мерные вектора, во внутренних узлах подпространства.
• При вставке весь путь до листового элемента лочится на чтение (совместной блокировкой), а сам листовой элемент — на запись (эксклюзивно). То бишь допиливать gistinserttuples, чтобы она читала родительскую страницу, можно смело, потому что она залочена на чтение.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.

— Виталий Филиппов • 01:33, 13 мая 2011 • нет комментариев