A system and method for building a hierarchical table is described. According to one embodiment, sorted data is stored within, or otherwise associated with, a newly created leaf node. The leaf node is then added to the table in a manner that ensures that after the addition is completed, all leaf nodes within the table will reside at a same level within the table hierarchy. Thus, the table is constructed in a balanced manner, and no re-balancing of the table is required after table construction has been completed. According to another aspect, a balanced table may be constructed incrementally such that users are allowed to access data stored within the table while additional, related data is added to a second table that is later merged with the table. This incremental approach may adapted to construct unbalanced, as well as balanced, tables.