Storing and Maintaining a TreeView in a file for random access and partial filling

Posted on 2007-04-01
Last Modified: 2010-04-01
I'm starting the design of a "Favorites" section to a plugin of mine.  Like a web browser, the favorite items can be organized in folders hierarchically and so forth.  The TreeView architecture and most of the GUI handling is already available and pretty straight forward.  But since memory is at a premium, I don't intend on fully structuring the Favorites hierarchy in memory but only showing the current displayed folders and visible items.  This means that access to the file (if that is recommended) that contains the full structure must be random and fast!

For illustration, this is what a full memory structure might contain:


But I only want the current visiblie folders/items in memory at any time:


This needs to be able to handle tens of thousands of items (minimally) and thus the reason for the partial TreeView filling and the need for quick access within the file that contains the full tree.  I've done this partial listing successfully for a real folder hierarchy tree, but now the hierarchy will be virtual.

Internet Explorer uses a 'virtual' folder hierarchy on the filesystem.  Firefox uses XML (I think).  I'd rather not do this the IE way - unless it is highly recommended!

Systems: Windows, MacOSX (VC++ 6, VS 2005, CodeWarrior 9, XCode 2.4.1)
Language: C++
GUI and other support: Cinema 4D C++ SDK (R8.2-R10)

I'd appreciate any links, pointers, algorithms in regards to such a process.

Thank you very much,
Question by:RTempleton
  • 2
LVL 16

Accepted Solution

AlexNek earned 84 total points
ID: 18833139
It is a little bit stragne wish for a favorites structure becaus it can't be hunderts Mb.
You can clreate three nodes on disk too. Instead pointers use data offset in file.
LVL 45

Assisted Solution

by:Kent Olsen
Kent Olsen earned 83 total points
ID: 18835609
Hello RTempleton,

I agree with Alex that this is a bit odd, but you've got your reasons so let's run with it.  :)

If your list contains a few hundred (or even a few thousand) items, you should probably abandon any plan to "page" the items in the TreeView yourself.  The lower level routines can do this a lot faster than you can.  Plus, the delay to the user will be less.  An application that forces a noticable delay to the user whenever a mouse button is pressed won't win too many quality points.  If you're TreeView is managing 1,000 items of approximately 200 bytes, the total structure size is only about 200K.  That's less than 1/3 the memory that was available on the old 16-bit DOS systems (640K).

If the list is large (in the megabytes range) Windows will transparently do its own paging of the data.  That is still faster than the application can do.  With the added benefit that as the user bounces around the list the recently accessed nodes are still in memory.

If the list is huge (10s of megabytes) you might consider mapping the file to memory with CreateFileMapping() so that you can quickly, and randomly, access the items within the file.  The nodes in the file would take on a linked list effect to allow you to quickly move through the nodes and build the current structure.

typedef struct
  int   ID;             // unique identifier given to this node.  Probably the ordinal within the file.
  int  Next;          // ID of the next item at this level
  int  Child;          // ID of the first child item to this node.
//  Your definitions

Given this data and structure (with record ID values):

  1,  My Name
  2,    Address
  3,    Phones
  4,      HomePhone
  5,      WorkPhone
  6,      CellPhone
  7,  YourName
  8,    Address
  9,    Phones
10,      HomePhone
11,      WorkPhone
12,      CellPhone

The data structures could look like this for ID, Next, and Child:

  1,   7,   2,  My Name
  2,   3,   0,  Address
  3,   0,   4,  Phones
  4,   5,   0,  HomePhone
  5,   6,   0,  WorkPhone
  6,   0,   0,  CellPhone
  7,   0,   8,  YourName
  8,   9,   0,  Address
  9,   0, 10,  Phones
10, 11,   0,  HomePhone
11, 12,   0,  WorkPhone
12,   0,   0,  CellPhone

This is the same technique that the TreeView uses to maintain the tree structure.  The only real benefit that can be derived from building it "on demand" is that you can split the time required to prebulid the entire list into smaller chunks that occur when a new node is selected.

Good Luck,
LVL 39

Assisted Solution

itsmeandnobodyelse earned 83 total points
ID: 18835963
You might use a database rather than file. The table would have an indexed column to have direct access to each folder of the tree. (e. g. base0/base1/..../folder). The folder *path* easily could be built in the GUI. The item entries could be stored in a BLOB column (or CLOB if text only) what made it one db call to fetch the items. Note, if there is not enough memory to hold the maximum of items possible, you could put all items to a separate table and have a reference to the folder table:

Table:         FOLDER

Table:         ITEM

You would fetch all data to a folder by


You could fetch the data in portions so you don't need the memory to hold all data.

The last isn't as fast as the BLOB or CLOB solution but fast enough if we assume that you can show only 30 items to a time. If you want to have a fast scroll you could add an index number in the ITEM table to be able to access ranges of items.

For the DBMS you could use Berkeley DB which most likely is fastest (though you need two calls cause it doesn't provide joint selects) or any other RDBMS which was supported at the target platforms. When using ODBC access you could switch the RDBMS depending on the platform.

Regards, Alex
LVL 16

Expert Comment

ID: 18837980
Database using is good idea too but I would like to use only one table, such as


because we always need to get one level Items. First you get all items for parent 0 /root/, then for that node that must be expanded.

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Displaying an arrayList in a listView using the default adapter is rarely the best solution. To get full control of your display data, and to be able to refresh it after editing, requires the use of a custom adapter.
Whether you've completed a degree in computer sciences or you're a self-taught programmer, writing your first lines of code in the real world is always a challenge. Here are some of the most common pitfalls for new programmers.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

828 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question