Suggested indices for a MPTT table

Question

I'm just building a table to store hierarchical data using the Modified Pre-order Tree Traversal (MPTT) -- you know the one: each node stores the left and right IDs to find its descendants. I'm using a the CakePHP suggested model, which varies from the standard way by including the parent_id with each row.

Here's the suggested table structure:

CREATE TABLE categories (
    id INTEGER(10) UNSIGNED NOT NULL AUTO_INCREMENT,
    parent_id INTEGER(10) DEFAULT NULL,
    lft INTEGER(10) DEFAULT NULL,
    rght INTEGER(10) DEFAULT NULL,
    name VARCHAR(255) DEFAULT '',
    PRIMARY KEY  (id)
);

Having never used this style before, and not knowing exactly how it gets searched, I'm wondering which fields I should be indexing? Is just the primary key sufficient, or should I be including lft and rght too?

Answer 1

i generally index just the left column. i usually work with mysql, which only allows for one index user per table in an execution plan, and an index on left helps every query i've ever written for a MPTT table and the benfits of including right in that index are minimal.

in short, a single index on left, in my experience, is the optimum balance between insert/update speed and select speed for nearly every use case.

Answer 2

You will always be using the left column, however I often need to find all leaf nodes.

WHERE lft = (rgt -1)

So I usually just create a index with the pair lft, rgt.