Когда не нужно применять рекурсию при работе с базами данных или умная работа с деревьями

Страница для печатиСтраница для печати

Рассмотрим решение типичной задачи при разработке например интернет магазинов - необходимо создать каталог товаров. Количество единиц товара в каталоге ~ 2000 или более. Все товары разбиты на категории с максимальной глубиной вложенности допустим 7. Если у категории товаров есть подкатегории то выводит необходимо все товары нижних уровней (подкатегорий).

Типичный ответ на подобные вопросы в интернете - "применяй рекурсию" или "ууууу..... здесь надо применять рекурсию .... это будет тяжелый алгоритм" Пока количество товаров небольшое рекурсия вполне справляется со своей задачей - ходит по категориям и выводит товары с приемлемой скоростью. Как только количество товаров и глубина вложенности растет - происходит резкое падение производительности и возрастает количество необходимой памяти для работы алгоритма.

В статье я расскажу как решить данную проблему.

В данной задаче меню представляет собой дерево категорий товаров связанное отношениями отец-сын то-есть таблица menu с полями:

  • id - идентификатор пункта меню (первичный ключ)
  • patent_id - идентификатор родительского пункта меню
  • lebel - название пункта меню

У пунктов меню верхнего уровня patent_id = -1, то-есть при поднимании по дереву от листьев к родителям признаком окончания подъема вверх является patent_id = -1. Перечень товаров каталога хранится в таблице goods которая имеет следующие поля:

  • id - идентификатор записи (первичный ключ)
  • articul - артикул товара
  • name - название товара
  • price - цена товара
  • menu_id - id  пункта меню  к которому относится товар (внешний ключ на таблицу menu )

Каждый из товаров привязывается при импорте или добавлении к какому-то пункту меню - поле menu_id. Скорость работы выборки  при большом количестве товаров в каталоге и применении рекурсии низкая. Для повышения скорости применим следующий метод:

В таблицу товаров для каждого уровня вложенности добавляем поле L1....L<i>- id  пункта меню  к которому относится товар на <i> уровне вложенности (внешний ключ на таблицу menu )

Для заполнения этих полей выполняем рекурсивный проход по категориям товара снизу вверх (пока patent_id != -1), но так как количество уровней вложенности для каждого товара не известно, то значения временно сохраняем в массив, а затем читая с конца разносим по полям ... причем L1 - последний элемент массива L2 - предпоследний и т.д. 

Теперь для быстрой выборки товаров  категории с подкатегориями необходимо лишь передавать id  пункта меню и текущий уровень при изменении положения в каталоге и выполнять выборку из таблицы товаров, где L<i>=id  пункта меню

Вроде все ..... пользуйтесь ...

Чуть позже выложу код реализации на PHP+MySql

Спасибо за внимание

Записаться на курсы английского языка SkyEng

Оставить комментарий

 
Подписаться на школьный портал