Adjacency List - для 1-2 уровневого меню.
Nested Sets (или Nested Trees) - для всего, что серьезней. Перестроение один раз, но выборка родителей и прочего гораздо удобней и без рекурсий\хранимых процедур.
Есть еще Mathearilzed Path - но там с хранением пути не очень, да и выборки так себе.
Для Yii2 есть шикарное решение:
https://github.com/paulzi/yii2-auto-tree