Database design for a tree: selection by parent, by layer or both -

i want store tree (i.e. each item has 1 parent, or none root node) of homogeneous items in relational database. there occasional writes tree, leaf node added somewhere , less intermediate node added.

two 2 common types of query are:

1. select items have specific parent.
2. select items are in specific layer / @ specific depth in tree.

storing parent of each item (null root node), first case easy. second case i'd have iterate , count parents of each item until reach root node, or store layer explicitly, introducing redundancy.

what options structure of database? database may have couple of thousand entries. goal make both types of queries fast.

this solution databases support recursive common table expressions (anything mysql really).

you should use adjacency list:

create table foo (   id int primary key,   name text not null,   parent_id int null references foo(id) ); 

your query this:

with recursive expression1 (    --select root node:   select     id,     name,     1 level   foo       parent_id null    union    select     current.id,     current.name,     previous.level + 1 level   foo current   join expression1 previous on current.parent_id = previous.id )  select * expression1   level = ?; 

this calculates level every row in table, might possible optimize it, i'm not sure how. materialized view option.

working example: http://sqlfiddle.com/#!15/ad19f/10