Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium


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

Posted on 2007-04-01
Medium Priority
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 336 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 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 332 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 332 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

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

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

Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may he…
The SignAloud Glove is capable of translating American Sign Language signs into text and audio.
Introduction to Processes
Screencast - Getting to Know the Pipeline

564 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