A few years ago I built a dodgy little site at Usenet.com.au that rendered Australian text Usenet newsgroups. While the front-end is offline, it'll be back online sometime in the future. One of the biggest challenges I faced in the early days was orientated around optimizing threaded articles. With several million articles in the database it quickly became evident that the original method of storing and displaying articles was problematic. It was slow, queries were long and complicated, and CPU resources were quite high.
My solution (for a small satellite website) came in the way of a simple class written by Jon Gales of JonGales.com . I've modified Jon's code myself and it works great. There are a lot of threaded comment classes around the place (including one within WordPress available for use under the GPL) but I found that Jon's was simply easy to use and implement for my quick and dirty solution.
The code is designed to be implemented into your own PHP project.
John's original code is below.
Here's example usage with the comment data provided as an array.