ansy
ничуть не хуже, если сделать нормально, древовидность это лишь явная(известная сервису) связь между комментариями(кто кому на что ответил) и возможно представление в интерфейсе в виде дерева(как на многих сайтах, или встраиваемых disqus комментариях)
соответственно после отображения таких комментариев доступен браузерный полнотекстовый поиск, кроме того с такими возможностями он будет редко нужен, ведь всегда можно посмотреть кто, где и на что вам ответил и тп, ветки отдельных дискуссий не перемешиваются(или легко различимы)

и всё же главное не отображение в виде дерева, а именно однозначность структуры на сервере, что бы в интерфейсе можно было просто перейти от сообщения к ответам на него и наоборот.
А для поиска можно сделать отдельное поле ввода.