How do I create nested categories in a Database?

I am making a videos website where categories will be nested:

e.g. Programming -> C Language -> MIT Videos -> Video 1
     Programming -> C Language -> Stanford Video -> Video 1
     Programming -> Python -> Video 1

These categories and sub-categories will be created by users on the fly. I will need to show them as people create them in the form of a navigable menu, so that people can browse the collection easily.

Could someone please help me with how I can go about creating such a database?

Solution

Quassnoi said :

You should use either nested sets or parent-child models.

I used to implement both of them. What I could say is:

Use the nested set architecture if your categories table doesn't change often, because on a select clause it's fast and with only one request you can get the whole branch of the hierarchy for a given entry. But on a insert or update clause it takes more time than a parent child model to update the left and right (or lower and upper in the example below) fields.

Another point, quite trivial I must admit, but:
It's very difficult to change the hierarchy by hand directly in the database (It could happen during the development). So, be sure to implement first an interface to play with the nested set (changing parent node, move a branch node, deleting a node or the whole branch etc.)

Here are two articles on the subject:

Last thing, I didn't try it, but I read somewhere that you can have more than one tree in a nested set table, I mean several roots.