This design was not mentioned yet:
Though it has limitations, if you can bear them, it's very simple and very efficient. Features:
- Columns: one for each lineage level, refers to all the parents up to the root, levels down from the items level are set to NULL
- Limit to how deep the hierarchy can be
- Cheap ancestors, descendants, level
- Cheap insert, delete, move of the leaves
- Expensive insert, delete, move of the internal nodes
Here follows an example - taxonomic tree of birds so the hierarchy is Class/Order/Family/Genus/Species - species is the lowest level, 1 row = 1 species:
CREATE TABLE `taxons` (
`TaxonId` smallint(6) NOT NULL default '0',
`ClassId` smallint(6) default NULL,
`OrderId` smallint(6) default NULL,
`FamilyId` smallint(6) default NULL,
`GenusId` smallint(6) default NULL,
`Name` varchar(150) NOT NULL default ''
);
and the example of the data:
+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name |
+---------+---------+---------+----------+---------+-------------------------------+
| 254 | 0 | 0 | 0 | 0 | Aves |
| 255 | 254 | 0 | 0 | 0 | Gaviiformes |
| 256 | 254 | 255 | 0 | 0 | Gaviidae |
| 257 | 254 | 255 | 256 | 0 | Gavia |
| 258 | 254 | 255 | 256 | 257 | Gavia stellata |
| 259 | 254 | 255 | 256 | 257 | Gavia arctica |
| 260 | 254 | 255 | 256 | 257 | Gavia immer |
| 261 | 254 | 255 | 256 | 257 | Gavia adamsii |
| 262 | 254 | 0 | 0 | 0 | Podicipediformes |
| 263 | 254 | 262 | 0 | 0 | Podicipedidae |
| 264 | 254 | 262 | 263 | 0 | Tachybaptus |
This is great because this way you accomplish all the needed operations in a very easy way, as long as the internal categories don't change their level in the tree.