Help:Tree Structures
Comparisons:
Hierarchical Data Storage Technique Comparisons
Efficient tree model implementations for Django (Adjacency List, Materialized Path and Nested Sets): http://django-treebeard.googlecode.com/svn/docs/index.html
Hierarchical data in RDBMSs: http://troels.arvin.dk/db/rdbms/links/#hierarchical
Modeling a Tree in a Document Database: http://seancribbs.com/tech/2009/09/28/modeling-a-tree-in-a-document-database/
Four ways to work with hierarchical data: http://evolt.org/node/4047/
Options for Storing Hierarchical Data in a Relational Database: http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database
Adjacency list vs. nested sets: http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/
Some answers to some common questions about SQL trees and hierarchies (Joe Celko): http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html
Storing Hierarchical Data in a Database: http://blogs.sitepoint.com/hierarchical-data-database/
how to store and navigate hierarchies: http://stackoverflow.com/questions/38801/sql-how-to-store-and-navigate-hierarchies
Algorithms for Management of Nested Set Data Model: http://forums.oracle.com/forums/thread.jspa?threadID=1659509
A Flexible Tree Structure: http://www.tonymarston.net/php-mysql/tree-structure.html
Trees in SQL: Nested Sets and Materialized Path: https://communities.bmc.com/communities/docs/DOC-9902
most efficient/elegant way to parse a flat table into a tree?: http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree/192462#192462
Nested Sets AKA Modified Pre-order Tree Traversal
Nested Sets design AKA "Modified Pre-order Tree Traversal" (left and right columns for numbering):
- easy to retrieve data, hard to add data
- Moving nodes is difficult because it requires renumbering all other nodes to the right (can use -number trick to speed up a bit)
- Efficient to retrieve a fully ordered hierarchical tree, Typically, a read/traverse/retrieve operation requires a single simple SQL statement
- Model very well adapted to implement tree structures with databases (whatever that means... indexing.. views?)
- Allows for compact and elegant implementations with nice code symmetries
- Inefficient model to modify tree structure. Typically, an insert/reorder operation requires an SQL statement that modifies n/2 nodes at the average, or n nodes in the worst case (n = # nodes in a tree)
- Non-intuitive database values. A simple db query of a table doesn't intuitively reveal the tree structure. As a consequence, nested set trees need to be handled and interpreted programmatically
Adjacency List Design AKA Recursion
Adjacency List Design AKA Recursion (columns like parent_id and level):
- hard to retrieve data, easy to add data
- you have both an ID column and a Parent ID column in a table. This is easy to understand and maintain but can be difficult or inefficient when you want to retrieve hierarchies of records.
- hard to retrieve a fully ordered hierarchical tree
- more-intuitive database values (parent id, depth)
Closure Table Design
http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html
Flat Table Design
http://www.ferdychristant.com/blog//articles/DOMM-7QJPM7
http://www.codeproject.com/KB/database/nestedsets.aspx
http://www.kamfonas.com/id3.html
http://replay.web.archive.org/20081121131640/http://www.dbmsmag.com/9603d06.html
http://troels.arvin.dk/db/rdbms/links/#hierarchical
http://roojs.com/blog.php/View/179/nested%20trees%20in%20mysql%20-%20handy%20stored%20procedures.
http://www.devx.com/tips/Tip/22127
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
http://www.tonymarston.net/php-mysql/tree-structure.html
http://www.sqlsummit.com/AdjacencyList.htm
http://explainextended.com/2009/07/22/hierarchial-queries-in-mysql-identifying-trees/
http://onlamp.com/pub/a/onlamp/2004/08/05/hierarchical_sql.html?page=2
https://communities.bmc.com/communities/docs/DOC-9902
http://stackoverflow.com/questions/5725914/mysql-recursive-tree-search
http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
http://www.devx.com/tips/Tip/22127
http://www.codeproject.com/KB/database/TreeStructureWithDatabase.aspx
http://blogs.sitepoint.com/hierarchical-data-database/
http://en.wikipedia.org/wiki/Hierarchical_database_model
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
XML DB's:
http://en.wikipedia.org/wiki/Sedna_%28database%29
http://xml.apache.org/xindice/
NoSQL:
http://redis.io/topics/introduction
Top DBA Shell Scripts for Monitoring the Database: https://communities.bmc.com/communities/docs/DOC-9942
IMS: https://communities.bmc.com/communities/docs/DOC-9908
Efficient lineage tracking for scientific workflows: http://portal.acm.org/citation.cfm?doid=1376616.1376716
