Добрый день, уважаемые читатели.
Сегодняшняя статья будет посвящена сравнению моделей работы с иерархическими данными в PostgreSQL, через Django приложение. В статья я специально не использую чистую реализацию в базе данных, т. к. меня интересует именно производительность в среде, приближенной к боевой.
Всего 2 часа назад я дописал последний тест к новому типу связи для PHPixie ORM — Nested Set. Я долго думал использовать ли этот подход или же Closure Table для хранения деревьев в SQL базах. Но в результате Closure Table проиграл ввиду квазиквадратических размеров к которым растет таблица связей (при 20 нодах в худшем случае уже можно получить 190 записей). Так что следующей задачей стала оптимизация классического Nested Set подхода, и результат мне очень даже понравился.
Привет ребят, давайте для начала проверим вашу память. Итак:
«На море на океане есть остров, на том острове дуб стоит, под дубом сундук зарыт, в сундуке — заяц, в зайце — утка, в утке — яйцо» в яйце — смерть Кощея!
А теперь, внимание, вопрос — как это формализовать?
Как приатачить к яйцу иголку и какова временная сложность детача смертии моей. Как перенести сказку в быль, как это выглядит на B-деревьях и почему на самом деле нет разницы между 2D и 1D.
А было все так: давным давно, в неком царстве, некотором государстве, на одном сервисе с шейрингом геолокации очень захотелось Иванушке Дурачку на уровне ЧПУ разделить Москву(/RU/MOW/) и Область(/RU/MOS/). И вообще навести порядок, чтобы все лежало по полочкам красиво и по алфавиту. Но не получалось ему сокровища свои посчитать, и аккуратно разложить. А Василису, хоть и дурак, к сбережениям не пускал.
Но решение было найдено.
Совсем недалеко над каким-то златом успешно чах Чахлик, еще и смерть он свою прятал по науке.
И если задача определения региональной (точнее полигональной) принадлежности некой иголки к некому сундуку выходит за рамки данной статьи, то нам ничто не мешает погрузиться в глубины зайца и посмотреть как он устроен на табличном уровне.
PS: и не спрашивайте почему зайца.
Читать полностью »
Приветствую!
Рад сообщить, что в прошедшие выходные, после долгого затишья, состоялся релиз моей небольшой, но смею надеяться, полезной поделки — гема TheSortableTree (rails 3, rails 4).
TheSortableTree — это гем, который помогает организовать отрисовку Nested Set деревьев. Но самое главное то, что он позволяет легко и просто управлять вашим Nested Set деревом с помощью удобного перетаскивания элементов в нужное место.
В текущей версии гема решена самая главная проблема — скорость отрисовки. Раньше она была чудовищно медленной. Сейчас (в среднем) можно получить скорость отрисовки 1500-2000 узлов в секунду. Я считаю эту скорость приемлемой и достаточной для большинства прикладных нужд.
Ниже (если вам интересно) немного истории создания гема, благодарности, планы, и рассказ о том, как на open source проекты влияет распитие крепкого черного чая вечером после работы.
P.S:
Anonym, возможно, ты будешь удивлен, но в этом релизе гема самую большую роль я отвожу тебе, хотя, я тебя практически не знаю и, возможно, ты никогда не программировал на ruby.
Деревья в базах данных можно хранить тремя основными методами: Adjacency List, Matherialized Path & Nested Set. Когда мы хотим переехать с AL на NS, это можно сделать с помощью рекурсии (если БД расово верная). Но что делать в случае MySQL?Читать полностью »
TheSortableTree — гем, реализующий функционал Drag&Drop для деревьев построенных на основе гемов awesome_nested_set или nested_set.
В 2008 году, когда мы делали свою первую социалку на рельсах, я впервые столкнулся гемом better_nested_set. Гем был прекрасен (я имею ввиду по сути, не по коду, реализация тогда еще хромала) и, пожалуй, одного только его было достаточно, что бы убедить меня забыть программирование на PHP, как страшный сон.
Мы использовали гем для формирования многоуровневого дерева комментариев. Но было одно но… В тот момент не было ни одного хелпера, который бы позволял отрисовывать эти деревья. Из-за этого приходилось выдумывать свои велосипеды.Читать полностью »
