Nested Intervals и их реализация под Yii2

    Привет, Хабр!
    Большинство разработчиков знает, что такое Nested Sets, их сильные и слабые стороны. Сегодня я хочу представить на суд общественности реализацию модификации этой методики, которая частично решает недостатки оригинального алгоритма, правда имеет и свои отрицательные стороны.

    Какие же плюсы и минусы у оригинальных Nested Sets:
    + быстрая выборка родителей и детей простым запросом;
    + быстрая выборка соседних узлов простым запросом;
    + быстрая выборка пустых узлов простым запросом;
    + моментальное получение количества всех детей в узле по формуле;
    + возможность не рекурсивного построения дерева одним циклом;
    — очень медленная вставка и обновление.

    Каковы же причины медленной вставки/обновления? Так как, значения границ узлов идут непрерывно, то любая вставка, особенно в начало дерева, требует перерасчёта границ всех последующих узлов. Если таблица достаточно большая, то это процесс может затянуться на десятки секунд и даже дольше. На анимации:


    Nested Intervals


    Первая мысль, которая пришла в голову, рассматривая картинку с визуальным представлением Nested Sets: «так границы же можно не двигать, если представить корневой узел как отрезок на поле вещественных чисел». То есть, если представить, что границы корневого узла имеют значения 0.0 и 1.0, то можно добавлять узлы в любое место не двигая другие, надо просто взять вещественное число между целевыми узлами. Но, так как мы прекрасно знаем, вещественные числа в компьютере имеют свои пределы, то от этой идеи я быстро отказался, в пользу целых чисел.

    С целыми числами суть та же, только границы корневого узла сделаем от нуля до INT_MAX. Тогда при вставке нового узла мы просто берём любые два незанятых значения между целевыми узлами, и больше ничего не трогаем, всё было бы быстро и круто, если бы не одно «но» — что делать если свободных значений больше нет? Очевидно, что нужно двигать все значения границ до ближайшего свободного значения, «расчищая» себе пространство для вставки. Только вот поиск такой «дырки» — задача затратная, поэтому результат в таком случае может выйти даже медленнее, чем в классических nested sets.


    Немного погуглив, я понял, что не изобрёл велосипед, и эта идея уже давно имеет название Nested Itervals. Только вот реализаций я так и не нашёл, т. к. на большинстве ресурсов данную методику рассматривали в негативном ключе, мол «одно лечим, другое калечим». И это не безосновательно, но мне стало очень интересно, захотелось протестировать в чём данный алгоритм лучше, а в чём хуже, и на сколько.

    Реализация


    Я начал писать Behavior для Yii2, реализующий идею Nested Intervals. Первая сложность возникла при написании методов вставки — как получить границу соседнего узла или родителя при insertBefore() и insertAfter() и границу первого/последнего узла при prependTo() и appendTo()? Если в Nested Sets она очевидна — +1/-1 к границе текущего узла, то здесь без дополнительно запроса к базе никак. Но благо, что выборки у нас быстрые.

    Достаточно много времени ушло на реализацию поиска незанятого места, на случай, если места на вставку нового узла не хватает. Зато в результате я получил возможность двигать границы не половины базы, а лишь небольшого кусочка до почти ближайшей «дырки» от текущего отрезка.

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

    Но вот перемещение из другого дерева — задача оказалась трудно решаемая, т. к. перемещаемых узлов может оказаться очень много, и вставлять их по одному обычным алгоритмом выходит слишком долго. Сначала я вообще хотел отказаться от этой возможности, списав на сложность реализации. Но чуть позже, осознал необходимость метода optimize(), который бы равномерно распределял границы существующих узлов по диапазону. После этого, возникла идея перемещать узлы другого дерева путём оптимизации исходного дерева с заготовлением «окна» под перемещаемые узлы. Всё это работает очень медленно (на данный момент есть оптимизация этого метода только под MySQL), но стоит отметить, что операция по перемещению из других деревьев требуется редко, куда чаще требуется движения в рамках одного дерева.

    Зато реализовывать выборки было достаточно легко — главные методы получения родителей и детей идентичны классическим nested sets. Чуть посложнее с выборками предыдущего/следующего соседа — требуется два запроса: получение родителя, и непосредственный поиск в диапазоне с лимитом. А вот совсем плохо стало с получением пустых узлов getLeaves(), т. к. пришлось его делать с помощью left join, что наверняка скажется на производительности.

    Оптимизация вставки


    Выполнив первый ряд тестов на производительность, результаты мягко говоря не впечатлили. Дело оказалось в том, что сначала я реализовал выбор границ вставляемого узла просто разбив отрезок на три части. Из-за этого промежуток для новых узлов стремительно сокращался. Так как диапазон 32 битного PHP составляет [0 — 2147483647] (операции с большими числами конвертируются во float), то выполнив вставку через appendTo() всего 19-ти узлов в корень, на 20-й узел уже не останется места (2147483647/3^19 = ~1.9), и приходится выполнять медленные операции по поиску незанятых мест и перемещения. Так дело, конечно, не пойдёт. Нужны какие-то оптимизации по распределению места. Для этого в Behavior есть аж 5 опций:
    • Первая и главная amountOptimize — этот параметр определяет на какое количество узлов запланировать разбиение доступного для вставки отрезка. То есть, при значении 20, мы сможем вставить 20 дочерних узлов, и они равномерно займут диапазон родителя, а дальше — как получится.
      В качестве значения можно использовать массив, тогда значение будет разным для каждого уровня.
    • noPrepend, noAppend, noInsert — эти параметры помогают оптимизировать резервирование места между границами, и положение первого узла. Если у вас, используется в основном только операция appendTo() (например, комментарии), то вы можете выставить noPrepend = true и noInsert = true, и тем самым значительно снизите вероятность возникновения тяжёлого случая с расчисткой пространства под новый узел. Более наглядно влияние этих параметров показано на картинках.
      amountOptimize=3
      amountOptimize=3
      noPrepend=true
      amountOptimize=3
      noAppend=true
      amountOptimize=3
      noInsert=true
      amountOptimize=3
      noInsert=true
      noPrepend=true
      amountOptimize=3
      noInsert=true
      noAppend=true

      Стоит отметить, что если вы задаёте noPrepend = true — это не значит, что вы не сможете выполнить вставку prependTo(), просто с большой долей вероятности множество таких операций будут выполняться медленно.
    • И последний параметр reserveFactor, определяет размер промежутков между границами. При единичке размер промежутка равен размеру вставляемого узла. Если сценарий использования Behavior предполагает большого числа операций insertBefore() и insertAfter(), то этот параметр лучше увеличить

    После всех этих манипуляций тесты стали гораздо более «вкусными».

    64 бита


    Если вы задействуете BIGINT колонки для хранения left и right атрибутов и используете 64-битный PHP, то сможете воспользоваться бесплатной оптимизацией в виде более широкого диапазона. Просто задайте параметр range = [0, 9223372036854775807]. Это позволит сделать более редкими случаи с недостатком места под новые узлы.

    Тесты на производительность


    В качестве эталона для сравнения, был взят самый популярный Behavior, реализующий Nested Sets от уважаемого Alexander Kochetov (Creocoder) creocoder/yii2-nested-sets. Так же было интересно сравнить результаты с Adjacency List с сохранением возможности сортировки. Подходящей библиотеки я для этого не нашёл, поэтому взял и написал сам (да ещё и с поддержкой JOINов, но сейчас не об этом).

    Первые два теста довольно синтетические, т. к. в реальности так заполнять дерево вряд ли кто будет, но мне данная процедура была необходима в первую очередь для генерации более-менее большой базы для дальнейших тестов. В них просто последовательно заполняются уровни фиксированным количеством детей.
    Результаты тестов 1 и 2
                                                    Запросов    DB время    Выполнение  Память
    Тест 1. Заполнение 3 уровня по 12 детей.
        Nested Sets                                 7696        6,961 ms    26,305 ms   135.8 MB
        Itervals default (amount=10)                6377        2,850 ms    11,920 ms   87.3 MB
        Itervals x64 default (amount=10)            5813        1,992 ms    10,963 ms   78.7 MB
        Itervals amount=24                          5813        1,765 ms    10,442 ms   78.7 MB
        Itervals amount=12 noPrepend noInsert       5813        1,750 ms    10,223 ms   78.7 MB
        Adjacency List                              5811        1,567 ms    9,591 ms    71.3 MB
        
    Тест 2. Заполнение 6 уровня по 3 детей.
        Nested Sets                                 4735        5,701 ms    19,784 ms   82.2 MB
        Itervals default (amount=10)                3644        1,275 ms    5,976 ms    48.9 MB
        Itervals amount=3 noPrepend noInsert        3644        1,271 ms    5,993 ms    48.9 MB
        Adjacency List                              3642        982 ms      5,812 ms    44.5 MB
    

    Уже в первом тесте видно, как плохо влияет неподходящее значение параметра amountOptimize. В 32-битном тесте появились лишние запросы? связанные с тем, что для некоторых узлов скрипт «расчищал место». Но тем не менее, даже в этом случае всё выполнилось гораздо быстрее. Кстати 64-бита в этом тесте выручили, и не было ни одной «плохой» ситуации.

    Тесты 3-5 имитируют вставку 20 узлов в разное место большой таблицы:
    Результаты тестов 3-5
                                                    Запросов    DB время    Выполнение  Память
    Тест 3. Вставка в начало <4% (20 в 19657 узлов)
        Nested Sets                                 100         15,597 ms   16,636 ms   5.0 MB
        Itervals                                    82          21 ms       150 ms      4.7 MB
        Adjacency List                              100         170 ms      439 ms      4.6 MB
    
    Тест 4. Вставка в середину >46% <50% (20 в 19657 узлов)
        Nested Sets                                 100         8,200 ms    8,985 ms    5.0 MB
        Itervals                                    82          269 ms      593 ms      4.7 MB
        Adjacency List                              100         163 ms      454 ms      4.7 MB
    
    Тест 5. Вставка в конец >96% (20 в 19657 узлов)
        Nested Sets                                 100         549 ms      911 ms      5.0 MB
        Itervals                                    83          46 ms       187 ms      4.7 MB
        Adjacency List                              106         159 ms      435 ms      4.7 MB
    

    Тест на вставку в начало базы очень наглядно демонстрирует слабое место классических Nested Sets — для вставки в начало базы требуется обновление границ всей базы. Отсюда и разгромный результат. Лишь результаты вставки в конец базы более-менее конкурирует с Nested Itervals. И кстати, обратите внимание на то, что Adjacency List был медленнее, это связано с тем, что для обеспечения сортировки, ему приходится выполнять SELECT MAX(sort).

    Следующий тест удаляет 20 узлов из начала дерева:
    Результаты теста 6
                                                    Запросов    DB время    Выполнение  Память
    Тест 6. Удаление из начала <4% (20 из 19657 узлов)
        Nested Sets                                 100         16,554 ms   17,678 ms   4.8 MB
        Itervals                                    60          164 ms      250 ms      4.2 MB
        Adjacency List parentJoin=0 childrenJoin=0  60          169 ms      257 ms      3.8 MB
        Adjacency List parentJoin=3 childrenJoin=3  60          87 ms       162 ms      3.8 MB
    

    Здесь ситуация аналогичная тесту 3. Есть лишь разница в том, что в Itervals при удалении уже не могут возникнуть «плохих ситуаций».

    Тест 7 очень показательный, т. к. хорошо имитирует использование Behavior для комментариев. В цикле 1000 узлов добавляется в случайно выбранный узел, с ограничением уровней. Тест 8 аналогичный, но с ещё более жесткими условиями — разрешено не только добавление, но и любая другая операция.
    Результаты тестов 7 и 8
                                                    Запросов    DB время    Выполнение  Память
    Тест 7. appendTo() в случайный узел (5 уровней, 1000 узлов)
        Nested Sets                                 5002        5,989 ms    17,406 ms   80.7 MB
        Itervals default (amount=10)                8497        23,301 ms   41,060 ms   120.7 MB
        Itervals x64 default (amount=10)            7092        11,330 ms   23,618 ms   97.5 MB
        Itervals amount=200,25 noPrepend noInsert   4009        1,431 ms    6,490 ms    50.2 MB
        Itervals x64 amount=250,30 noPrepend noIns  4003        1,421 ms    6,615 ms    50.0 MB
        Adjacency List                              4001        1,062 ms    5,976 ms    46.1 MB
        
    Тест 8. произвольная операция в случайный узел (5 уровней, 1000 узлов)
        Nested Sets                                 5002        9,383 ms    23,502 ms   80.7 MB
        Itervals default (amount=10)                7733        8,123 ms    24,031 ms   107.2 MB
        Itervals x64 default (amount=10)            5663        3,761 ms    14,084 ms   75.6 MB
        Itervals amount=200,25 reserve=2            4175        1,548 ms    7,223 ms    52.8 MB
        Itervals x64 amount=250,30 reserve=2        4003        1,541 ms    6,753 ms    50.0 MB
        Adjacency List                              4395        4,394 ms    12,377 ms   53.4 MB
    

    Тут в глаза бросается то, как важно при задействовании Intervals правильно настроить параметры оптимизации вставки, т. к. в данном примере настройки по умолчанию дали очень печальный результат. Зато с оптимизациями всё работает очень быстро, сопоставимо с Adjacency List. Кстати в 8 тесте он сильно замедлился, т. к. для обеспечения сортировки ему тоже требовалось «расчищать место».

    Следующие два теста на перемещение узлов в дереве:
    Результаты тестов 9 и 10
                                                    Запросов    DB время    Выполнение  Память
    Тест 9. Перемещение узлов в начале <4% (20 из 19657 узлов)
        Nested Sets                                 200         24,312 ms   25,479 ms   6.3 MB
        Itervals                                    160         180 ms      573 ms      6.0 MB
        Adjacency List                              111         107 ms      318 ms      4.6 MB
    
    Тест 10. Перемещение узлов из конца в начало <4% >96% (20 из 19657 узлов)
        Nested Sets                                 200         16,999 ms   17,973 ms   6.3 MB
        Itervals                                    160         16,972 ms   17,854 ms   6.0 MB
        Adjacency List                              108         86 ms       325 ms      4.6 MB
    

    В принципе, что у Nested Sets, что у Nested Intervals эта операция должна выполняться за одинаковое время, но в коде у Creocoder это происходит не оптимально, т. к. вместо того, чтобы просто поменять местами пару блоков, в его коде сначала двигается вся база до конца, потом идёт перемещение нужного блока, а затем опять вся база двигается назад. Зато у Creocoder можно использовать unsigned поля для атрибута depth, а в моём Behavior он временно при перемещении становится отрицательным. Результаты перемещения из конца в начало сопоставимы, а вот Adjacency List имеет значительное преимущество.

    После написания Behavior мне захотелось узнать, какую выгоду даст использование Trait вместо поведений. Поэтому я портировал его Trait со статическими атрибутами. Дальнейшие тесты на выборки велись также и в вариантах с Trait. Но результаты применения примесей мягко говоря не впечатлили, особенно учитывая то, насколько более уродлив стал код из-за них.
    Простая выборка всех элементов Model::find()->all():
    Результаты теста 11
                                                    Запросов    DB время    Выполнение  Память
    Тест 11. Выбор всех узлов (19657 шт.)
        Nested Sets                                 1           40 ms       1,108 ms    215.2 MB
        Itervals                                    1           42 ms       1,247 ms    225.3 MB
        Itervals Trait                              1           41 ms       1,174 ms    207.4 MB
        Adjacency List                              1           33 ms       890 ms      179.1 MB
    

    Этот тест был написан в первую очередь для сравнения потребления памяти Behavior vs. Trait. И как видим разница есть, но незначительная.

    Выборка потомков:
    Результаты теста 12
                                                    Запросов    DB время    Выполнение  Память
    Тест 12. Выбор детей и потомков (для 819 узлов в середине дерева из 19657 узлов)
        Nested Sets                                 1641        6,397 ms    7,498 ms    24.9 MB
        Itervals Behavior                           1641        579 ms      1,657 ms    25.0 MB
        Itervals Trait                              1641        615 ms      1,590 ms    24.3 MB
        Adjacency List parentJoin=0 childrenJoin=0  2562        720 ms      1,969 ms    36.9 MB
        Adjacency List parentJoin=3 childrenJoin=3  2461        704 ms      1,966 ms    35.3 MB
    

    Запросы на выборку детей должны быть одинаковыми в Nested Sets и Nested Intervals, но здесь раскрылся ещё один недостаток библиотеки от Creocoder — не оптимально выбираются потомки. Потомков можно было выбрать моментально используя индекс по одному из атрибутов left или right `lft` > :leftValue && `lft` < :rightValue, вместо этого, индекс используется лишь на половину `lft` > :leftValue && `rgt` < :rightValue. Если проанализировать EXPLAINом, становится ясно, что первый вариант гораздо более предпочтителен. Результаты Adjacency List уступают, что неудивительно.

    Выборка предков:
    Результаты теста 13
                                                    Запросов    DB время    Выполнение  Память
    Тест 13. Выборка родителей (для 819 узлов в середине дерева из 19657 узлов)
        Nested Sets                                 821         3,344 ms    4,069 ms    20.6 MB
        Itervals Behavior                           821         3,292 ms    4,147 ms    22.0 MB
        Itervals Trait                              821         3,310 ms    4,080 ms    21.1 MB
        Adjacency List parentJoin=0 childrenJoin=0  3180        948 ms      2,304 ms    51.2 MB
        Adjacency List parentJoin=3 childrenJoin=3  1641        486 ms      1,495 ms    30.8 MB
    

    Здесь Nested Sets и Nested Intervals ведут себя одинаково, и достаточно медленно. Дело в отсутствии нормальных индексов и неудачным стечением обстоятельств — оба индекса из середины таблицы имеют много элементов. Adjacency List как не удивительно, отработал быстрее, хоть и за счёт памяти (хотя тут дело ещё в простом 3-х уровневом дереве).

    Выборка соседних и пустых узлов:
    Результаты теста 14 и 15
                                                    Запросов    DB время    Выполнение  Память
    Тест 14. Выборка соседних узлов (для 819 узлов в середине дерева из 19657 узлов)
        Nested Sets                                 1641        520 ms      1,424 ms    24.3 MB
        Itervals Behavior                           1641        19,681 ms   21,326 ms   27.5 MB
        Itervals Trait                              1641        19,666 ms   21,251 ms   26.5 MB
        Adjacency List parentJoin=0 childrenJoin=0  1641        535 ms      1,442 ms    23.7 MB
        Adjacency List parentJoin=3 childrenJoin=3  1641        508 ms      1,421 ms    23.6 MB
    
    Тест 15. Выборка пустых узлов (для 819 узлов в середине дерева из 19657 узлов)
        Nested Sets                                 821         3,215 ms    3,814 ms    18.8 MB
        Itervals Behavior                           821         10,450 ms   11,166 ms   18.8 MB
        Itervals Trait                              821         10,425 ms   11,040 ms   18.7 MB
        Adjacency List parentJoin=0 childrenJoin=0  1833        568 ms      1,743 ms    32.6 MB
        Adjacency List parentJoin=3 childrenJoin=3  1732        556 ms      1,891 ms    31.3 MB
    

    Тут, как и предполагалось, мы видим слабые стороны Nested Intervals. Как говорится, без комментариев.


    Выводы


    Nested Intervals — имеет право на жизнь. У него есть как преимущества, так и недостатки:
    + быстрая вставка (при условии хорошего подбора оптимизирующих параметров);
    + быстрое удаление узла с потомками;
    + такая же скорость как у Nested Sets в выборке предков и потомков;
    + так же, осталась возможность не рекурсивного построения дерева одним циклом;
    — медленное получение соседних узлов;
    — медленное получение пустых узлов;
    — нет возможности моментально подсчитать количество потомков в узле.

    Реализация для Yii2


    Хочу отметить, что методы немного отличаются от предложенных в поведении Creocoder. Во-первых я изменил именование методов на геттеры getParents() getDescendants(), это позволяет реализовывать доступ к связанным узлам, аналогично Relations, что позволяет не делать вторичных запросов к базе:
    $node = Node::findOne(['name' => 'test']);
    $children = $node->children; // relation
    $children = $node->getChildren()->all(); // query
    

    Кроме того, я не стал протаскивать Yii-шные параметры к save($runValidation, $attributeNames), вместо этого я реализовал методы, как указание на действие (прямо как ->asArray()->):
    $node = new Node();
    $node->makeRoot()->save(false);
    $node->insertAfter($node2)->save();
    

    Реализация Nested Intervals на GitHub.
    Реализация Adjacency List на GitHub.
    Поделиться публикацией

    Похожие публикации

    Комментарии 13

      0
      Я начинал эту тему когда-то, но забросил.
      остановился на чуть упрощенном НС.
      У меня немного денормализовано выходит, но производительность сильно выигрывает.
      Есть поле для сортировки в рамках «братьев», чтобы не переставлять деревья, и есть поле уровень, в котором указывается уровень каждого элемента. Это упрощает поиск элементов одного уровня, а также прямых потомков (не внуков и правнуков).
      Сейчас всего уже не упомню, но за счет некоторой избыточности я получил хорошую скорость на все запросы.

      Что касается основной оптимизации для интервалов, которую я хотел делать, так это использование строковых индексов.
      В рамках СУБД нам реально нужно только сравнение. Да, хочется сделать иногда «индекс + 100500 где индекс < 1000500», но тут можно выкрутится хранимыми процедурами, да и такая дорогая операция будет относительно редкой.

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

      Ну это в теории, на практике я до этого так и не дошел.
        0
        Полностью подписываюсь, можно обойти все минусы если добавить поле для хранения предка и порядка сортировки.
          0
          Ага. А еще убрать left, right и назвать это Adjacency List.

          Если я правильно понимаю вашу мысль, то при таком подходе изменения в таблице станут еще более дорогостоящими. При перемещении ветви необходимо будет обновить не только поля left и right, но еще и поле с id предка и поле с порядком сортировки у братьев на том уровне откуда была удалена ветвь и куда вставлена.
            0
            Как я понял, Ekstazi предлагает в дополнение к Nested Sets добавить поля parent_id и sort. Правда я не пойму как это поможет справиться с долгой вставкой в начало дерева.
            А если убрать left и right действительно получится Adjacency List, именно такой и используется в статье для сравнения.
              0
              Часто упоминается о том, что комбинация Nested Sets и Adjacency List выигрышна в плане скорости различных выборок (ветки, родителя, детей и т.д.), но в противовес усложняется модификация. На сколько я понял, цель у автора была как раз ускорить модификацию дерева.

              А для чего хранить порядок сортировки если есть поле left что-то я пока не пойму.

              UPD: не заметил что вы и есть автор.
                0
                я писал свой коммент про эти минусы:
                — медленное получение соседних узлов;
                — нет возможности моментально подсчитать количество потомков в узле. (я так понял прямых)
                Ускорить же операции вставки, я так понимаю, не получится, но для неё есть другие способы хранения дерева и другие инструменты(например, графовые бд, оператор connect by, и т.д. )
                  0
                  Статья как раз о том, как ускорить вставку при этом сохранив главные преимущества Nested Sets (причём не привязываясь к определённой БД).
                  подсчитать количество потомков в узле. (я так понял прямых)

                  Нет, вообще имелось в виду всех потомков. В классических Nested Sets это можно узнать по формуле (right - left - 1) / 2.
                    0
                    Ускорить вставку может ТЕКСТОВЫЙ left/right. У вас будет такой большой диапазон, что за него не нужно будет особенно заморачиваться.
                  0
                  Порядок сортировки я хранил потому, что мне лично операция изменения порядка была нужна часто, а она слишком дорогая. Именно потому что есть left который нужно менять у всех, и как следствие у всех потомков.
                +1
                При перемещении да. Но это не очень частая, и всё равно не очень дорогая операция. Братьев конечное количество, менять всех нет необходимости, только тех кто старше «подвинуть», да и то, только там куда переносим, нам ведь не нужно чтобы номера шли подряд, и с нуля/единицы… А это делается одним запросом. Не очень дорогим. Изменение ид предка? Ну да. У оной записи меняется еще на одно поле больше, помимо left/right.

                Не соглашусь с Экстези, что так можно обойти ВСЕ ограничения. Увеличением разрядности left/right можно добиться гораздо большего прироста скорости. Насколько я помню полноценная индексация текстовых полей до 1024 бит включительно поддерживается всеми публичными БД. А 1024 бит это огого… даже если у нас на один уровень будет до 1024 страниц, то мы можем спокойно до первого конфликта позволить себе десять уровней вложенности… Для многих задач идеально.
                  0
                  Да, на счёт текстовых/BLOB left и right тоже была мысль. Но решил остановиться на более простой реализации.
                  Если по конкретнее, то я думал все подсчёты вести через bcmath, а затем конвертировать результат в текстовый/BLOB вид при сохранении в базу. В принципе, переписать не особо долго, но так как усложняются расчёты на стороне php, то это лучше делать как ещё один вариант behavior.
                    0
                    Только есть минусы в текстовых left/right — чрезмерный расход памяти и места, сложность вычислений. Кроме того, наверняка будут сложности с тем, что база может не учитывать регистр при сравнении строк, и нужны будут специфические ее настройки или хранить значения не экономно. А с BLOB вообще лучше не связываться)
                    В общем, идея повысить разрядность хорошая, но боюсь подводных камней будет много.
                      0
                      Ну вот как раз с регистром проблемы я не вижу.
                      Если с БД будут сложности, и нормально не настроить, то просто меняем метод конвертации числа в текст, и чуть уменьшаем размерность.
                      Помню была задача использовать GUID вместо инкрементального идентификатора, чтобы не было конфликтов у полунезависимых баз, которые синхронизируются эпизодически, и не хотелось заниматься сложным механизмом восстановления связности при перенумерации. Идентификатор у нас соответственно в 128 бит, как обычно и делается.
                      Это 16 байт BLOB, или 32 символа в шестнадцатеричном текстовом виде.
                      16 байт это нормально, 32 — уже жадность не позволяет.
                      Взял base64, отбросил знаки равно. Получил 22 символа.
                      Приемлемо.
                      Потом мне надоели слеши в идентификаторах, и я решил что base62 меня устроит больше. Поиск готовых функций, чтобы не изобретать велосипед, переписывание двух методов и написание миграции для живых данных заняло минут 15.
                      Потом 5 минут выполнения миграции, еще 20 минут ругани на себя, и писания второй миграции которая меняет все связи всех таблиц. Еще 10 минут запуска, и еще неделя на организационные моменты с запуском миграций на всех реплик.
                      В общем если не делать таких телодвижений по горячему, и с распределенной системой, то никаких проблем.
                      А если сделать поведение с «драйверами индекса» то вообще прозрачно будет.
                      Тут главное провести тест, оправданы ли мои ожидания с текстовыми индексами. Может реальный тест вообще будет медленнее.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое