Trees in the database: Advanced data structures

Storing tree structures in a bi-dimensional table has always been problematic. The simplest tree models are usually quite inefficient, while more complex ones aren't necessarily better. In this talk I briefly go through the most used models (adjacency list, materialized path, nested sets) and introduce some more advanced ones belonging to the nested intervals family (Farey algorithm, Continued Fractions, and other encodings). I describe the advantages and pitfalls of each model, some proprietary solutions (e.g. Oracle's CONNECT BY) and one of the SQL Standard's upcoming features, Common Table Expressions.

Trees In The Database - Advanced data structures from Lorenzo Alberton

Lorenzo Alberton

Lorenzo Alberton Lorenzo has been working with large enterprise UK companies for the past 10+ years and is currently CTO at DataSift. He's an international conference speaker and a long-time contributor to many open source projects. Lorenzo Alberton's profile on GitHub Lorenzo Alberton's profile on LinkedIN View Lorenzo Alberton's profile on PHP PEAR
View Lorenzo Alberton's Twitter stream Lorenzo Alberton - Sun Certified MySQL 5 Developer PHP5 ZCE - Zend Certified Engineer


AJAX, Apache, Book Review, Charset, Cheat Sheet, Data structures, Database, Firebird SQL, Hadoop, Imagick, INFORMATION_SCHEMA, JavaScript, Kafka, Linux, Message Queues, mod_rewrite, Monitoring, MySQL, NoSQL, Oracle, PDO, PEAR, Performance, PHP, PostgreSQL, Profiling, Scalability, Security, SPL, SQL Server, SQLite, Testing, Tutorial, TYPO3, Windows, Zend Framework