Задача — организовать хранение некоего каталога, с достаточно разветвлённой структурой (дерево) — пускай это будет каталог продукции интернет-магазина. Для поиска элемента доступен только URI вида "/category/subcategory/another-category/and-one-more-category". Максимальная вложенность порядка 10.
Категории запрашиваются часто, меняются редко, общее количество категорий может быть порядка 100 тыс.
Так же требуется шустрая генерация «хлебных крошек». Причём ссылка на категорию («and-one-more-category») может отличаться от её заголовка («И ещё одна категория»), который используется для вывода на странице.
У меня пока одно предполагаемое решение — «в лоб» — по следам Materialized path:
таблица для категорий имеет следующую структуру
CREATE TABLE categories (
`id` INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
`title` VARCHAR(50) NOT NULL,
`link` VARCHAR(50) NOT NULL,
`path` VARCHAR(1000) NOT NULL,
`title_path` VARCHAR(1000) NOT NULL
)
CREATE INDEX path_indx ON categories (`path`);
`title` — заголовок категории («И ещё одна категория»),
`link` — ссылка категории («and-one-more-category»),
`path` — путь к категории («category/subcategory/another-category/and-one-more-category»),
`title_path` — то же, что и `path`, только содержит заголовки соответствующих категорий — для быстрой генерации «хлебных крошек»
— Привлекает то, что для поиска категории не нужно никаких усилий — просто SELECT… WHERE path LIKE…
— Не пугает даже необходимость перестроения путей в случае перемещения/переименования узлов.
— Пугает избыточность подхода и вероятные размеры таблицы при большом количестве категорий. Насколько это скажется на скорости?
— Так же смущает то, что в качестве ключа для поиска используется такая длинная строка в `path` (хотя я очень сомневаюсь что она когда-либо выйдет за пределы 100 символов)
Может вынести `path` и `title_path` в отдельную таблицу? Так всё равно путь и хлебные крошки для категории требуется практически всегда, так что придётся джойнить…
Смотрю в сторону Full hierarchy, но опять же смущает возможная избыточность в таблице иерархии, тем более учитывая потенциальные количества категорий и уровни вложенности.
нужно ли предусматривать возможность изменения родительской категории, например при редактировании подкатегории (category/subcategory/… на category/subcategory-1/)? если нет, то возможно Ваш вариант подходит. Если надо предусмотреть эту возможность, да и вообще иметь более гибкую структуру — советую погуглить nested sets
100 000 категорий — это 5 символов на узел в пути. 10*5 — максимальный путь на категорию.
Итого максимум 5 мегабайт данных. Реально — в разы меньше.
Не тот размер, о котором стоит переживать.
Касательно CRC32 и md5
Во-первых, md5 — это в hex-представлении 32 символа на хеш, а в Base64 представлении итого меньше.
Но по сравнению с максимумом в 50 символов, какой-то сомнительный выигрыш, экономите на копейках.
Во-вторых, каким образом тогда собираетесь использовать LIKE для поиска?
md5(«abc») — это не like concat(md5(«ab»), '%')
Могу посоветовать использовать смешанный подход, в как DaBase. См. реализацию.
Т.е. там задействуется как Nested Sets принцип (что ускоряет выборку дочерних элементов), также у каждого узла имеют место быть параметры parent_id и level.
My<cod/>.net
