Тут уже дважды назвали nested sets — но он имеет большие накладные расходы на изменение данных. Хотя, 10к комментариев — редкость вроде, так что шевелиться должен весьма шустро.
habrahabr.ru/post/46659/
Для комментариев, даже для mysql (с постресом куда веселее с его рекурсивными запросами) — лучше, имхо, подойдёт именно Adjacency List (т.е. именно та структура, что вы и прикинули). Но строить дерево придётся уже в логике приложения — выбираете всю таблицу и строите массив[ parent_id ][] = узел. При выводе уходите в рекурсию.
