Hucoder
March 6th, 2008, 11:02 AM
Hi
I have a data structure that is pretty much complete and serving its purpose, but I'd like to know it's formal name.
It is akin to the page frame tables used in an OS virtual memory manager.
Looking up item "x" involves walking a tree composed of nodes that have arrays of pointer (e.g. 1000 pointers) to other similar nodes, with the data itself being stored in leaf nodes.
This data structure supports:
InsertItem(&data);
AccessItem(345);
RemoveItem(2118);
The structure allows you to treat it as a collection, AccessItem(345) returns the 345th item NOT "element 345" (This distinction is important). If I called RemoveItem(100) then the 345th item would not be the same item as it would have been before we deleted item 100.
The design is pretty much working, it is faster than an AVL tree and supports enumeration (in-order traversal) that is very very much faster than an AVL tree, which was a goal (This enables very fast .NET 'foreach' enumeration of massive external data sets).
Four "tiers" using 1000 entries per node, can support up to 1000^4 or 10^12 items.
Anyway, so what is the name of this kind of structure, like I say similar to a virtual memory managers page frame database.
Thx
I have a data structure that is pretty much complete and serving its purpose, but I'd like to know it's formal name.
It is akin to the page frame tables used in an OS virtual memory manager.
Looking up item "x" involves walking a tree composed of nodes that have arrays of pointer (e.g. 1000 pointers) to other similar nodes, with the data itself being stored in leaf nodes.
This data structure supports:
InsertItem(&data);
AccessItem(345);
RemoveItem(2118);
The structure allows you to treat it as a collection, AccessItem(345) returns the 345th item NOT "element 345" (This distinction is important). If I called RemoveItem(100) then the 345th item would not be the same item as it would have been before we deleted item 100.
The design is pretty much working, it is faster than an AVL tree and supports enumeration (in-order traversal) that is very very much faster than an AVL tree, which was a goal (This enables very fast .NET 'foreach' enumeration of massive external data sets).
Four "tiers" using 1000 entries per node, can support up to 1000^4 or 10^12 items.
Anyway, so what is the name of this kind of structure, like I say similar to a virtual memory managers page frame database.
Thx