Nested Sets для Javascript

На любом современном сайте (да и на сайтах постарше) встречаются вложенные структуры, иерархия объектов, деревья. Самый распространенный пример — каталог.

Сегодня множество проектов разрабатывается с использованием Javascript. Как же хранить древовидные структцры в этом случае? Об этом и хотелось бы поговорить.

Сейчас передо мной стоит задача на основе параметров продукции составить иерархтческую структуру каталога.

Существуют различные алгоритмы для хранения деревьев и примером таких алгоритмов могут послужить Adjacency List, Matherialized Path, Nested Set и Closure Table.

Если посоветуете еще какие-то — буду рад услышать и поучиться.

Когда я писал расширения для Joomla я часто использовал Nested Set. Именно в этой CMS я впервые встретил эту модель. Но теперь стек поменялся и сейчас это Javascript. Привычки остались, да и сайты на Joomla тоже. Нужно переносить данные на новые сервисы и проекты.

О Nested Sets довольно много информации в интернете и при желании вы всегда сможете ее найти, но тем не менее пару слов о этой модели данных я должен сказать.

Смысл Nested Set в том, что у каждого узла в иерархии существует пара ключей левый ключ и правый ключ. В зависимости от их значений осуществляется обход дерева. Положительными качествами алгоритма, на мой взгляд, является быстрота выборки данных. В этом алгоритме нет рекурсии. В то же время для изменения структуры дерева, добавления, удаления и переноса узлов, необходимо пересчитывать все ключи.

Чтобы использовать данные из Nested Set в проектах на Javascript нужен модуль который умел бы работать с этой моделью.

Поискав через npm я нашел модули, функционалом которых была выборка данных из структуры Nested Sets, т.е. все ключи уже должны были быть проставлены. Была необходимость править структуру, но такой возможности я не нашёл.

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

Таким образом одна и та же категория (данные категории) может лежать в разных родителях. Это позволит пользователям находить то, что они ищут быстрее при хорошо продуманной иерархии.

Хотя с точки зрения SEO появятся две страницы с разными URL и с одинаковым контентом, но это можно решить каноническими ссылками.

Если это не правильно — прошу SEO-специалистов меня поправить.

В итоге я решил написать модуль и опубликовать его на npmjs.com.

Если кому-то пригодится — буду очень рад.

Сейчас я продолжаю работать над ним и в планах реализовать перенос узла по дереву.

Вот ссылка на npm, где вы можете скачать пакет.

Вот ссылка на github, где вы можете скачать исходники.

Документация есть и там и там.

Буду рад любым комментариям.

Хороших вам проектов и интересных задач.

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

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

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

    0
    Позволю себе совет. Перепишите на typescript. Ну и еще один, попросите опытных товарищей сделать codereview вашему коду. Я пробежался по диагонали, есть явные места где стоит чуть переделать, например
    //....
     return nstd.Structure.sort((a, b) => {
          if (a.lkey > b.lkey) return 1
          if (a.lkey < b.lkey) return -1
          return 0
        })
    
    // better replace with 
     return nstd.Structure.sort((a, b) => a.lkey - b.lkey )
    

    уверен что будут и более веские замечания.
      0
      Большое спасибо, обязательно займусь
      0

      Это какой-то ужас, а не код...


      Вот примеры того, как код писать нельзя:


        _nestedsets.removeItem = function (itemId) {
           // ...
           for (var i = 0; i < nstd.Structure.length; i++) {
              if (nstd.Structure[i].itemId === itemId) {
                var childs = nstd.getChilds(nstd.Structure[i]._id)
      
      // ...
      
       _nestedsets.getChilds = function (nodeId, depth) {
          var nstd = this
      
          var parentNode = nstd.getNode(nodeId)
      
        _nestedsets.getNode = function (nodeId, asCopy) {
          var nstd = this
      
          var selectedNode = nstd.Structure.filter(n => n._id === nodeId)

      Тут в массиве нод по индексу берётся _id, после чего сразу же в том же самом массиве выполняется по этому _id поиск...




                var childs = nstd.getChilds(nstd.Structure[i]._id)
                for (var j = 0; j < childs.length; j++) {
                  nstd.removeNode(childs[j]._id)
                }

      removeNode удаляет всё поддерево нод. Зачем тут вообще цикл и почему нельзя было написать просто nstd.removeNode(nstd.Structure[i]._id)?


      На пустом месте оквадратили линейный алгоритм!




          var childs = nstd.getNodes().filter(n => {
            return n.lkey >= parentNode.lkey && n.rkey <= parentNode.rkey && nodeId !== n._id && (depth === undefined ? true : n.depth <= (parentNode.depth + depth))
          })
      
          // ...
      
            childs.sort((a, b) => {
              if (a.lkey > b.lkey) return 1
              if (a.lkey < b.lkey) return -1
              return 0
            })

      getNodes() возвращает уже упорядоченный массив. Зачем его сортировать ещё раз по тому же самому свойству? С каких пор фильтрация сбивает сортировку?




            var results = []
            // ...
            .map(n => {
              n.data = nstd.Data[n.itemId]
              results.push(n)
            })
            childs = results

      Ну а .map(n => nstd.Data[n.itemId]) не судьба написать было? Зачем тут вообще массив results?


      И ещё вопрос: зачем использовать метод .map в качестве заменителя цикла for-of, если у массивов есть метод .forEach для тех же целей?




      И ещё один пример как не надо писать в том же самом месте, что и прошлые два.


          if (childs.length > 0) {
            var results = []
            childs.sort((a, b) => {
              if (a.lkey > b.lkey) return 1
              if (a.lkey < b.lkey) return -1
              return 0
            }).map(n => {
              n.data = nstd.Data[n.itemId]
              results.push(n)
            })
            childs = results
          }

      Зачем тут условный оператор? Что sort, что map на пустом массиве прекрасно работают. Если это была попытка оптимизации — то экономить надо в первую очередь на асимптотике, во вторую очередь на лишних массивах, и лишь в последнюю очередь на спичках.




      Ну и последнее


      var nstd = this

      Зачем так делать в 2020м году? В стрелочных функциях this не "теряется", и его больше не требуется подобным способом "беречь".


      Не говоря уже о том, что у вас уже есть переменная _nestedsets для тех же целей.

        0
        Большое спасибо за критику, она помогает развиваться.

        По поводу удаление ветки узлов, да вы абсолютно правы, внес изменения.
        С сортировкой опять же да, лишние сортировки не нужны, убрал.

        Что касается .map(n => nstd.Data[n.itemId]) позвольте не согласиться, эта конструкция вернет элемент из свйоства Data, а там храняться данные, а не узлы, мне же необходима информация по узлам. В качестве свойства data для каждого узла (как дополнение) я указывал элемент из свойства Data, но вся информация об узле также осталась.

        О использовании map вместо forEach, разница методов в том, что один вернет новый массив, а второй вернет undefined. Если говорить о скорости, то я видел тесты, где map значительно быстрее forEach. Возможно не прав, если так — поправьте.

        var nstd = this
        Да, полностью согласен, не нужно так

        Переписал все на Typescript.
        github.com/orxtime/nestedsetsjs/blob/typescript/src/nestedsets.ts

        Буду ждать от вас новых комментариев, спасибо.
          0
          Что касается .map(n => nstd.Data[n.itemId]) позвольте не согласиться, эта конструкция вернет элемент из свйоства Data, а там храняться данные, а не узлы, мне же необходима информация по узлам

          В таком случае вам тем более не нужен массив results, поскольку его содержимое совпадает с содержимым childs.


          О использовании map вместо forEach, разница методов в том, что один вернет новый массив, а второй вернет undefined. Если говорить о скорости, то я видел тесты, где map значительно быстрее forEach.

          Это весьма странная информация. Мне почему-то кажется, в тех тестах сравнивался одиночный map и комбинация forEach + push.

            0
            Убрал и childs. Теперь сразу return.

            По поводу Map vs forEach: проводил такой эксперимент

            const myAwesomeArray = Array.from({length: 1000}, (e,i) => i)
            
            console.time("forEachTest")
            myAwesomeArray.forEach(x => (x + x) * 10000000000)
            console.timeEnd("forEachTest")
            
            console.time("mapTest")
            myAwesomeArray.map(x => (x + x) * 10000000000)
            console.timeEnd("mapTest")
            


            Результаты такие:

            forEachTest: 0.123ms
            mapTest: 0.069ms

            forEachTest: 0.122ms
            mapTest: 0.078ms

            forEachTest: 0.127ms
            mapTest: 0.068ms
              0

              Ну а вот мой результат:


              forEachTest: 0.04296875 ms
              mapTest: 0.05078125 ms


              forEachTest: 0.052978515625 ms
              mapTest: 0.055908203125 ms


              forEachTest: 0.053955078125 ms
              mapTest: 0.057861328125 ms


              Ищите проблему в окружении. Может, где-то полифил неоптимальный стоит, или наоборот — нестандартный. Или транспайлер начудил. Или всё проще, и GC прибирает за прошлым map как раз во время forEach.

                0
                Последнее вряд ли, тесты запускал отдельно друг от друга. Буду разбираться. Спасибо.
            0

            Что же до вашего кода на Typescript — у вас там лишние классы NestedSetItem, NestedSetNode, NestedSetRootNode, NestedSetEmptyNode и NesteSetError (вместо них проще использовать литералы объектов, точно так же как вы на js делали). Кроме того, интерфейс INestedSet тоже лишний.


            Ну и какой нафиг module.exports? Проще всего export class NestedSet { ... } написать. Ну а если так важно экспортировать именно объект — конструкция export = new NestedSet() в помощь. Хотя в таком случае лучше вообще отказаться от класса и экспортировать отдельные функции:


            export function removeItem (itemId: number) {
              // ...
            }
            
            export function addNode (targetNodeId: number, itemId: number) {
              // ...
            }
              –1
              childs.sort((a, b) => {
                      if (a.lkey > b.lkey) return 1
                      if (a.lkey < b.lkey) return -1
                      return 0
                    })

              Пять копеек от меня:


              childs.sort((a, b)=>(+(a.lkey>b.lkey)-(a.lkey<b.lkey)))

              :)

            0
            iulanovy4, да, все верно. Если говорить конкретно о моей задаче то мне нужно осущиствить переход от MySQL (Joomla, Nested Set) на ElasticSearch (Nested Set) + MongoDB (Nested Set), попутно отредактировав структуру. Отсюда это решение. Возможно это можно использовать как хранилище на клиентской стороне (но это уже догадки).
              +1
              Все то, что вы назвали (Adjacency List, Matherialized Path, Nested Set и Closure Table), это способы хранения древовидных структур данных в реляционных базах. Зачем они в памяти?
                0
                Мне нужно осущиствить переход от MySQL (Joomla, Nested Set) на ElasticSearch (Nested Set) + MongoDB (Nested Set), попутно отредактировав структуру. Отсюда это решение.

                Возможно это можно было бы использовать как хранилище на клиентской стороне (но это уже догадки). Из БД подгружать данные на клиент и тот уже редактирует дерево, не нагружая при этом сервер. А когда редактирование завершено — записывает данные в БД. Тут конечно вопрос синхронизации с сервером.
                  0

                  А не проще ли в таком случае перейти от nested sets к нормальному древовидному виду, внести там изменения — и снова построить nested sets? Быстрее так точно:


                  function nestedSetsToTree(items) {
                      items.sort(...);
                  
                      let root = { rkey: +Infinity, data: { children: [] } };
                      let stack = [ root ];
                      let top = () => stack[stack.length-1];
                  
                      for (let { lkey, rkey, ...data } of items) {
                          data = { ...data, children: [] };
                          while (lkey >= top().rkey) stack.pop();
                          top().data.children.push(data);
                          stack.push({ rkey, data });
                      }
                  
                      return root.data.children;
                  }
                  
                  function treeToNestedSets(roots) {
                      let result = [];
                      let nextKey = 0;
                      for (let root in roots) visit(root);
                      return result;
                  
                      function visit({children, ...data}) {
                          let item = { lkey: nextKey++, ...data };
                          result.push(item);
                          for (let child in children) visit(child);
                          item.rkey = nextKey++;
                      }
                  }
                    0
                    В мыслях было сделать универсальный переходник между Adjacency List, Matherialized Path, Nested Set, Closure Table и нормальным деревом.
                0
                const maxId = Math.max(...this.Structure.map(o => o._id)) || 0

                Если будет слишком много элементов, случится Maximum call stack size exceeded
                reduce будет понадежнее, хотя и медленнее
                Но у вас уже используется map, и с учетом этого reduce будет уже быстрее чем map+rest arguments
                
                var arr = Array.from(Array(100000), () => ({_id: Math.round(Math.random() * 10000)}));
                console.time('reduce');// 1180ms
                for(var i = 0; i < 1000; i++)
                    arr.reduce((a,{_id}) => (a > _id ? a : _id), -Infinity)
                console.timeEnd('reduce');
                console.time('rest args');// 1748ms
                for(var i = 0; i < 1000; i++)
                    Math.max(...arr.map(x => x._id))
                console.timeEnd('rest args');
                


                Также || 0 выглядит как ненужная перестраховка
                Если элементов не будет, то вы получите -Infinity, и этот код не поможет
                В остальных случая _id вроде всегда число, а значит мы и так получим максимальный _id
                  0
                  Спасибо за рекомендации, поправил.

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

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