Просмотр исходного текста страницы Блог:Виталий Филиппов/2011-05-13 Пилим GiST

Пиля K-D-B-дерево для [http://www.sai.msu.su/~megera/postgres/gist/ GiST]'а в PostgreSQL, потихоньку его вкуриваю… Интересные вещи о нём:
* В 9.1 (сейчас бета), как я уже написал, есть поддержка поиска ближайших соседей, то есть просмотра дерева поиска в порядке возрастания удалённости от искомого элемента.
* Один из двух авторов — тот самый «индеец», [http://www.sai.msu.su/~megera/ Олег Бартунов].
* Размер страницы индекса в постгресе — обычно 8 Кб.
* Чтобы реализовать канонiчное KDB-дерево, а точнее — любое дерево поиска, в котором следующее разбиение пространства зависит от предыдущего, GiST нужно допилить (конкретно функцию gistinserttuples), чтобы picksplit’у передавался родительский узел, потому что в оригинале ему только передаётся список самих элементов, которые нужно разбить на две группы. Вот я щас как раз это допиливаю.
* Предикаты на нелистовых страницах модифицируются не '''после''' вставки элемента в листовую страницу, а '''до'''! Оно сразу, когда ищет, куда бы вставить элемент, сначала дёргает по всем элементам страницы penalty, выбирает элемент с минимальным, потом вычисляет union предиката и нового вставляемого элемента (O_o), и сохраняет, если в итоге получается другой предикат. Чуть-чуть не совсем логичная схема, если в вашем индексе внутренние и листовые узлы хранят разные типы ключей, но реализацию упрощает. Разные типы — то есть не как в R-дереве — в листах квадратики и во внутренних квадратики, а как например в KDB — в листах N-мерные вектора, во внутренних узлах подпространства.
* При вставке весь путь до листового элемента лочится на чтение (совместной блокировкой), а сам листовой элемент — на запись (эксклюзивно). То бишь допиливать gistinserttuples, чтобы она читала родительскую страницу, можно смело, потому что она залочена на чтение.
{{wl-publish: 2011-05-13 02:33:31 +0400 | VitaliyFilippov }}