Хранение деревьев в Mysql какие есть способы?

Question

[xolnimda]

Мне нужно хранить в базе дерево причем нужно чтобы последовательность можно было менять.
т.е. была возможность сортировки.

Что то типа такого

Математика
 - Теория вероятностей
 - Логика
Юриспруденция
- Административное право
- Трудовое право
Язык
- Русский
- Английский
- Испанский

например можно поменять местами Математика, Юриспруденция, Язык
Ну и так же можно было бы менять внутреннюю структуру, например поменять порядок Русский, Английский, Испанский.
Вложенностей может быть больше.

Что посоветуете?

Может есть какой готовый класс на php на все случаи жизни для работы с деревьями.
Очень важна скорость.

Answer 1

[Андрей Ежгуров]

Существует 4 основных способа хранения деревьев в реляционной БД:

Adjacency List - описан @Satanpit.

Matherialized Path - полный путь до узла хранится в виде строки типа 0035.0993.7324.1256 (т.е. узел верхнего уровня содержит строку 0035, узел второго уровня - строку 0035.0993 и т.д.)

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

Closure Table - отдельно храним данные, отдельно иерархию.

А ещё есть комбинации этих способов.

По всем этим способам в рунете (в том числе на хабре) существует большое количество информации.

Comments

[Mokhirjon Naimov]

Какой самый простой? Чуток почитал про Nested Sets и мне кажется он очень сложный.

[Ян Иванов]

Mokhirzon Naimov: на мой взгляд Closure Table — самый простой. Гляньте статьи: janiwanow.com/blog/closure-table-part-1 janiwanow.com/blog/closure-table-part-2

Answer 2

[Александр Хиренко]

Структура БД примерно такая:
id - id категории
parent_id - id родительской категории (0 для категории первой вложенности)
sort_id
name

Для выборки в PHP используйте рекурсию.

Примеров в сети валом

Answer 3

[Philipp]

У Joe Celko есть просто превосходная книга. Вообще он автор многих очень хороших книг по SQL.

Answer 4

[Павел Гоголинский]

Читайте в сторону Nested Set. Вот небольшая статья на хабре
habrahabr.ru/post/153861
Я по этой изучал www.getinfo.ru/article610.html
Можно поискать готовые расширения, если вы пишете на фреймворке. Вот отлиное для Yii
https://github.com/yiiext/nested-set-behavior

Answer 5

[Lemfidavr]

Отношение многие ко многим.
habrahabr.ru/post/193380