Nested Sets

Nested sets вызывает нагрузку при добалении элемента в дерево, а parent_id - при выводе дерева из БД.
Соответственно при большом и ветвистом дереве, например комментов лучше nested sets, а при построении списка категорий в админке (именнт так там и есть), лучше parent_id так как добавление комментария происходит реже чем просмотр страницы с комментариями, а категории в админке вообще после настройки редко смотрят.

UPD by Sander
Рассмотрим пример работы с parent_id.
Первый запрос, перебираем все комментарии к новости с parent_id равным нулю, т.е:

WHERE post_id={$post_id} AND parent_id=0

Внутри обработчика шаблона КАЖДОГО комментария делается еще один запрос за поиск подкомментариев, т.е. получаем цикл внутри цикла:

WHERE post_id={$post_id} AND parent_id={$row['id']}

Для наглядности, например имеем древовидную структуру комментариев:

• первый комм
  
  • ответ на первый комм
    
• второй комм
  
  • ответ на второй комм 1
    
    • ответ на ответ на второй 1 комм 1
      
    • ответ на ответ на второй 1 комм 2
      
  • ответ на второй комм 2
    
• третий комм
  
  • ответ на третий комм 1
    
    • ответ на ответ на третий 1 комм
      
  • ответ на третий комм 2
    
    • ответ на ответ на третий 2 комм
      
• четвертый комм
  

В nested sets это займет 1 запрос, в parent_id (что я видел) на это ушло бы 14 запросов. Общий запрос, плюс по 1 запросу на каждый комментарий.
Представили себе нагрузку при выводе 50, 100 комментариев?
Почему так много запросов? Потому что в каждом комментарии выполняется запрос на проверку существования комментариев с parent_id равным id обрабатываемого комментария.