Comments 13
Я начинал эту тему когда-то, но забросил.
остановился на чуть упрощенном НС.
У меня немного денормализовано выходит, но производительность сильно выигрывает.
Есть поле для сортировки в рамках «братьев», чтобы не переставлять деревья, и есть поле уровень, в котором указывается уровень каждого элемента. Это упрощает поиск элементов одного уровня, а также прямых потомков (не внуков и правнуков).
Сейчас всего уже не упомню, но за счет некоторой избыточности я получил хорошую скорость на все запросы.
Что касается основной оптимизации для интервалов, которую я хотел делать, так это использование строковых индексов.
В рамках СУБД нам реально нужно только сравнение. Да, хочется сделать иногда «индекс + 100500 где индекс < 1000500», но тут можно выкрутится хранимыми процедурами, да и такая дорогая операция будет относительно редкой.
ну а вычитание, сложение и деление строк в пхп сделать не сложно. Основная нагрузка всё-таки лежит на базу, а не на пхп.
Ну это в теории, на практике я до этого так и не дошел.
остановился на чуть упрощенном НС.
У меня немного денормализовано выходит, но производительность сильно выигрывает.
Есть поле для сортировки в рамках «братьев», чтобы не переставлять деревья, и есть поле уровень, в котором указывается уровень каждого элемента. Это упрощает поиск элементов одного уровня, а также прямых потомков (не внуков и правнуков).
Сейчас всего уже не упомню, но за счет некоторой избыточности я получил хорошую скорость на все запросы.
Что касается основной оптимизации для интервалов, которую я хотел делать, так это использование строковых индексов.
В рамках СУБД нам реально нужно только сравнение. Да, хочется сделать иногда «индекс + 100500 где индекс < 1000500», но тут можно выкрутится хранимыми процедурами, да и такая дорогая операция будет относительно редкой.
ну а вычитание, сложение и деление строк в пхп сделать не сложно. Основная нагрузка всё-таки лежит на базу, а не на пхп.
Ну это в теории, на практике я до этого так и не дошел.
Полностью подписываюсь, можно обойти все минусы если добавить поле для хранения предка и порядка сортировки.
Ага. А еще убрать left, right и назвать это Adjacency List.
Если я правильно понимаю вашу мысль, то при таком подходе изменения в таблице станут еще более дорогостоящими. При перемещении ветви необходимо будет обновить не только поля left и right, но еще и поле с id предка и поле с порядком сортировки у братьев на том уровне откуда была удалена ветвь и куда вставлена.
Если я правильно понимаю вашу мысль, то при таком подходе изменения в таблице станут еще более дорогостоящими. При перемещении ветви необходимо будет обновить не только поля left и right, но еще и поле с id предка и поле с порядком сортировки у братьев на том уровне откуда была удалена ветвь и куда вставлена.
Как я понял, Ekstazi предлагает в дополнение к Nested Sets добавить поля parent_id и sort. Правда я не пойму как это поможет справиться с долгой вставкой в начало дерева.
А если убрать left и right действительно получится Adjacency List, именно такой и используется в статье для сравнения.
А если убрать left и right действительно получится Adjacency List, именно такой и используется в статье для сравнения.
Часто упоминается о том, что комбинация Nested Sets и Adjacency List выигрышна в плане скорости различных выборок (ветки, родителя, детей и т.д.), но в противовес усложняется модификация. На сколько я понял, цель у автора была как раз ускорить модификацию дерева.
А для чего хранить порядок сортировки если есть поле left что-то я пока не пойму.
UPD: не заметил что вы и есть автор.
А для чего хранить порядок сортировки если есть поле left что-то я пока не пойму.
UPD: не заметил что вы и есть автор.
я писал свой коммент про эти минусы:
— медленное получение соседних узлов;
— нет возможности моментально подсчитать количество потомков в узле. (я так понял прямых)
Ускорить же операции вставки, я так понимаю, не получится, но для неё есть другие способы хранения дерева и другие инструменты(например, графовые бд, оператор connect by, и т.д. )
— медленное получение соседних узлов;
— нет возможности моментально подсчитать количество потомков в узле. (я так понял прямых)
Ускорить же операции вставки, я так понимаю, не получится, но для неё есть другие способы хранения дерева и другие инструменты(например, графовые бд, оператор connect by, и т.д. )
Статья как раз о том, как ускорить вставку при этом сохранив главные преимущества Nested Sets (причём не привязываясь к определённой БД).
Нет, вообще имелось в виду всех потомков. В классических Nested Sets это можно узнать по формуле
подсчитать количество потомков в узле. (я так понял прямых)
Нет, вообще имелось в виду всех потомков. В классических Nested Sets это можно узнать по формуле
(right - left - 1) / 2.Порядок сортировки я хранил потому, что мне лично операция изменения порядка была нужна часто, а она слишком дорогая. Именно потому что есть left который нужно менять у всех, и как следствие у всех потомков.
При перемещении да. Но это не очень частая, и всё равно не очень дорогая операция. Братьев конечное количество, менять всех нет необходимости, только тех кто старше «подвинуть», да и то, только там куда переносим, нам ведь не нужно чтобы номера шли подряд, и с нуля/единицы… А это делается одним запросом. Не очень дорогим. Изменение ид предка? Ну да. У оной записи меняется еще на одно поле больше, помимо left/right.
Не соглашусь с Экстези, что так можно обойти ВСЕ ограничения. Увеличением разрядности left/right можно добиться гораздо большего прироста скорости. Насколько я помню полноценная индексация текстовых полей до 1024 бит включительно поддерживается всеми публичными БД. А 1024 бит это огого… даже если у нас на один уровень будет до 1024 страниц, то мы можем спокойно до первого конфликта позволить себе десять уровней вложенности… Для многих задач идеально.
Не соглашусь с Экстези, что так можно обойти ВСЕ ограничения. Увеличением разрядности left/right можно добиться гораздо большего прироста скорости. Насколько я помню полноценная индексация текстовых полей до 1024 бит включительно поддерживается всеми публичными БД. А 1024 бит это огого… даже если у нас на один уровень будет до 1024 страниц, то мы можем спокойно до первого конфликта позволить себе десять уровней вложенности… Для многих задач идеально.
Да, на счёт текстовых/BLOB left и right тоже была мысль. Но решил остановиться на более простой реализации.
Если по конкретнее, то я думал все подсчёты вести через bcmath, а затем конвертировать результат в текстовый/BLOB вид при сохранении в базу. В принципе, переписать не особо долго, но так как усложняются расчёты на стороне php, то это лучше делать как ещё один вариант behavior.
Если по конкретнее, то я думал все подсчёты вести через bcmath, а затем конвертировать результат в текстовый/BLOB вид при сохранении в базу. В принципе, переписать не особо долго, но так как усложняются расчёты на стороне php, то это лучше делать как ещё один вариант behavior.
Только есть минусы в текстовых left/right — чрезмерный расход памяти и места, сложность вычислений. Кроме того, наверняка будут сложности с тем, что база может не учитывать регистр при сравнении строк, и нужны будут специфические ее настройки или хранить значения не экономно. А с BLOB вообще лучше не связываться)
В общем, идея повысить разрядность хорошая, но боюсь подводных камней будет много.
В общем, идея повысить разрядность хорошая, но боюсь подводных камней будет много.
Ну вот как раз с регистром проблемы я не вижу.
Если с БД будут сложности, и нормально не настроить, то просто меняем метод конвертации числа в текст, и чуть уменьшаем размерность.
Помню была задача использовать GUID вместо инкрементального идентификатора, чтобы не было конфликтов у полунезависимых баз, которые синхронизируются эпизодически, и не хотелось заниматься сложным механизмом восстановления связности при перенумерации. Идентификатор у нас соответственно в 128 бит, как обычно и делается.
Это 16 байт BLOB, или 32 символа в шестнадцатеричном текстовом виде.
16 байт это нормально, 32 — уже жадность не позволяет.
Взял base64, отбросил знаки равно. Получил 22 символа.
Приемлемо.
Потом мне надоели слеши в идентификаторах, и я решил что base62 меня устроит больше. Поиск готовых функций, чтобы не изобретать велосипед, переписывание двух методов и написание миграции для живых данных заняло минут 15.
Потом 5 минут выполнения миграции, еще 20 минут ругани на себя, и писания второй миграции которая меняет все связи всех таблиц. Еще 10 минут запуска, и еще неделя на организационные моменты с запуском миграций на всех реплик.
В общем если не делать таких телодвижений по горячему, и с распределенной системой, то никаких проблем.
А если сделать поведение с «драйверами индекса» то вообще прозрачно будет.
Тут главное провести тест, оправданы ли мои ожидания с текстовыми индексами. Может реальный тест вообще будет медленнее.
Если с БД будут сложности, и нормально не настроить, то просто меняем метод конвертации числа в текст, и чуть уменьшаем размерность.
Помню была задача использовать GUID вместо инкрементального идентификатора, чтобы не было конфликтов у полунезависимых баз, которые синхронизируются эпизодически, и не хотелось заниматься сложным механизмом восстановления связности при перенумерации. Идентификатор у нас соответственно в 128 бит, как обычно и делается.
Это 16 байт BLOB, или 32 символа в шестнадцатеричном текстовом виде.
16 байт это нормально, 32 — уже жадность не позволяет.
Взял base64, отбросил знаки равно. Получил 22 символа.
Приемлемо.
Потом мне надоели слеши в идентификаторах, и я решил что base62 меня устроит больше. Поиск готовых функций, чтобы не изобретать велосипед, переписывание двух методов и написание миграции для живых данных заняло минут 15.
Потом 5 минут выполнения миграции, еще 20 минут ругани на себя, и писания второй миграции которая меняет все связи всех таблиц. Еще 10 минут запуска, и еще неделя на организационные моменты с запуском миграций на всех реплик.
В общем если не делать таких телодвижений по горячему, и с распределенной системой, то никаких проблем.
А если сделать поведение с «драйверами индекса» то вообще прозрачно будет.
Тут главное провести тест, оправданы ли мои ожидания с текстовыми индексами. Может реальный тест вообще будет медленнее.
Sign up to leave a comment.
Nested Intervals и их реализация под Yii2