1

I'm developing a CI project that needs to outputs a perfect binary tree in HTML. Each node in the tree relates to a record in a table. The table currently has upwards of 10 million rows and I'm going to need to output a tree with depth of at least 9, so things could get slow quickly if it's not built optimally.

Using the CI's MVC paradigm, what's the best way to organize this data? With such a large table, I don't want to have to hit the database too many times, and building a tree like this can get costly very quickly (# cells = 2^(depth+1)-1).

So far I've built the controller to handle the request (easy part) and a library to handle/build the tree structure by recursively hitting the DB and creating an object for each node. I'm sorta stuck on how to organize the rest. Should I handle the tree traversal and HTML output from within a view/helper? If we do that, there's going to be a whole bunch of logic in the view(s) which I know people try to avoid. Similarly, I know it's looked down upon to output any HTML from within a library but given this structure it almost seems like it's logical to handle all the recursion/output from there.

Any advice would be very helpful, and thanks in advance!

tereško
  • 58,060
  • 25
  • 98
  • 150
Jeff
  • 6,643
  • 3
  • 25
  • 35
  • Use either nested sets or a transitive closure table. See [What is the most efficient/elegant way to parse a flat table into a tree?](http://stackoverflow.com/a/192462/623041) for more information. – eggyal Sep 15 '12 at 01:57
  • Thanks for the informative links. The nested set method seems like it's a little too bloated for my needs. The transitive closure looks like it's more fitting and could help speed up queries. I'll fiddle around with it and see if it helps. Now, I just need to come up with a clean MVC-type approach to output the table structure... – Jeff Sep 15 '12 at 03:14
  • So...with 10 million rows and having to store 9 levels deep, this is going to create a *massive* table. I don't think it's really viable. – Jeff Sep 15 '12 at 03:43
  • You could look into [partitioning](http://dev.mysql.com/doc/en/partitioning.html) to make a large table more manageable & performant; or else nested sets probably isn't as "bloated" as it first appears. I think that there are CI libraries out there which will implement nested sets for you, but I don't come from a CI background: perhaps others can make recommendations? – eggyal Sep 15 '12 at 10:07
  • What is the nature of the relationship of each record? Are they all one-to-many or are some only child records? Is the relationship already created in other tables? (Sorry for the questions, just trying to understand.) – seangates Sep 18 '12 at 01:31
  • Each row has an `id` with `left_parent` and `right_parent` (pseudo names). `left_parent` and `right_parent` correspond to an `id` in the same table. – Jeff Sep 18 '12 at 06:24
  • @Jeff I'm trying to do same kind of scenario did you find an answer for this, if you have submit the answer here please – Rasa Mohamed Jan 17 '21 at 08:32

0 Answers0