demiurg (demiurg) wrote,
demiurg
demiurg

Category:

SQL Trees (continued)

продолжаем Страсти по Деревьям.

RAL -- это моё собственное название, обозначающее Redundant Adjacency List.
это когда для кажой ноды дерева хранится ссылка не только на её непосредственного родителя, но и на всех остальных её родителей.

т.о., для ноды 1.3.5.12 в таблице со структурой дерева будут храниться записи (1.3.5.12 - 1.3.5), (1.3.5.12 - 1.3), (1.3.5.12 - 1).
избыточно, да, но зато можно легко одним запросом получить, скажем, всех потомков ноды, или вычислить путь от ноды до корня дерева, и даже... реализовать множественное наследование.

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

PostgreSQL 7.4 CygWin, леплю триггеры, оптимизирую таблицы и все запросы, чтобы было Как Надо™, добавляю 100К нод в дерево, случайным образом выбирая предка.

запустил скрипт утром, а после обеда оно как раз дошло до магического числа "фу-у, заебало!", которое по историческо-астрономическо-волшебным причинам всегда равняется в точности ("дохуя" / 2).
в общем, нажал я ^C, и...

добавилось 51 715 нод. (всего-то?!)
наибольшее кол-во нод "падало" в среднем на уровни с 9 по 13.
всего уровней в дереве получилось 25.
кол-во связей между нодами -- 580 847 (хуяссе!)
две таблички с этим деревом заняли на диске ~160М

и тем не менее, мне всё ещё нравится эта схема устройства дерева:
на вставке хоть и тормозит, но тормозит меньше, чем Вложенные Множества, зато на выборке инфы бегает резво.

выводы пока оставлю на потом...
может таки удастся ещё что-нибудь там соптимизировать.
Subscribe

  • последняя капля

    многие вещи в моей жизни проходят учёт по графе "похуй" в моей личной табели о рангах. это просто даёт возможность не обращать внимания на всякую…

  • про СУП

    забавно. вот я курю и стряхиваю пепел в пепельницу. даже не задумываюсь о ней, поглощённый совсем другими мыслями. и когда я в гости к кому-нибудь…

  • [йоптваю] менюшко в висте

    вынь-виста. кины всякие -- на линукс-сервере через самбу. в эксплорере давлю ПКМ на .avi -- тормоза, тормоза, Explorer (Not Responding), тормоза…

  • Post a new comment

    Error

    Comments allowed for friends only

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 29 comments

  • последняя капля

    многие вещи в моей жизни проходят учёт по графе "похуй" в моей личной табели о рангах. это просто даёт возможность не обращать внимания на всякую…

  • про СУП

    забавно. вот я курю и стряхиваю пепел в пепельницу. даже не задумываюсь о ней, поглощённый совсем другими мыслями. и когда я в гости к кому-нибудь…

  • [йоптваю] менюшко в висте

    вынь-виста. кины всякие -- на линукс-сервере через самбу. в эксплорере давлю ПКМ на .avi -- тормоза, тормоза, Explorer (Not Responding), тормоза…