Sunday, February 1, 2009

Data Structures: B*Tree

Hierarchy and Relational Databases Doesn't Scale well For Humans, they add Structure. They only scales well for an amount of structure that is feasible to learn.

I'm Writing a Library that contains some data structure useful for data indexing, this library will be the base for a simple FileSystem and it can be simply used by Applications to store and retrieve data efficently. Today I've finished the B*Tree Implementation, Now I've to implement something for full-text search like Suffix Tree or similar data structure.

Balanced trees are used in databases, and more generally, wherever a programmer needs to search and store to non-random memory by a key, and has the time to code it this way.

Internal Nodes

Internal nodes consist of pointers to sub-trees separated by their delimiting keys. The key that precedes a pointer to a sub-tree is a duplicate of the first key in the first formatted node of that sub-tree. Internal nodes exist solely to allow determining which formatted node contains the item corresponding to a key.

Leaf Nodes

Leaf nodes contains information, Information are stored in Items and each of which is identified by a key used to identify data and to keep sorted the tree. An item is a data container that is contained entirely within a single node, and it allows us to manage space within nodes. Every item has a key, an offset to where in the node the item body starts and a length of the item body.

If you want more information about this Project feel free to contact me, else you've to wait the first release of the project :)

No comments:

Post a Comment