Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win


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
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

Question has a verified solution.

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

This article will inform Clients about common and important expectations from the freelancers (Experts) who are looking at your Gig.
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Introduction to Processes

610 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