A little about the trees

Introduction

Have you met the situation when it is necessary to implement storage of a tree structure in a relational database?



Examples are many. This tree comments and product catalog, and settlements, divided by countries and regions. I think that everyone will be able to give a few examples.

In this topic we will talk about one of the opportunities that exist for the organization of storage of trees in PostgreSQL, ltree.

Installation

The installation process will be described for debian-like systems.

the
1. you need to install the package postgresql-contrib;
the
2. psql -U postgres -d database-name -1 -f SHAREDIR/contrib/ltree.sql add database database-name the contents of the module (SHAREDIR — the directory with shared data PostgreSQL)
the
3. ...
the
4. PROFIT!

Brief description

ltree allows you to store the tree structure in the form of a label, as well as provides opportunities to search them. [1, 2].

Mark may consist of Latin letters, digits, and underscores. Label can be way, which are stored in ltree.

Path label is a set of 0 or more labels separated by dots. To search tracks use the special requests lquery.

Examples lquery:

the
1. foo records by labels is exactly equal to foo;
the
2. foo.* records whose path label starts with foo;
the
3. *.foo.* — any recording path labels containing foo.

Modifiers lquery:

the
1. *{n} — path contains exactly n marks;
the
2. *{n,} — the path contains at least n tags;
the
3. *{n,m} — the path contains n to m label;
the
4. *{,m} — the path contains no more than m labels.

In addition, there are modifiers for tags:

the
1. foo* — any label starting foo;
the
2. foo@ — label, case-insensitive, for example: Foo, FOO, FoO — fit;
the
3. foo% choose foo_bar, but not choose foo and foobar.

Modifiers can be combined.

ltree is possible to compare between a and c lquery, i.e., the standard comparison operations =, < a>, >, <, >=, <= are fully supported. In addition they introduced several operations:

the
1. ltree @ > ltree — whether the left term of the expression ancestor right;
the
2. ltree < @ ltree — whether the left member of the expression is a descendant of the right;
the
3. ltree ~ lquery or lquery ~ ltree — whether ltree request lquery.

A complete list of operations and functions can be found in the official documentation [2].

Example usage

About the trees, what little we've learned. Let's try to implement the example.

The challenge before us is to implement the storage units in the form: country — region — city.

Create table:
the

create table "world" (
"id" serial primary key,
"name" varchar(150) not null,
"tree" ltree not null
);

Fill data:
the

 id | name | tree
----+----------------+-------
1 | Russia | 1
2 | US | 2
3 | Canada | 3
4 | Moscow | 1.4
5 | Khimki | 1.4.5
6 | Mytischi | 1.4.6

And now we have you, there's an easy way to get information. For example to get a list of all countries is sufficient to run the following query:
the

select "id", "name" from "world" where "tree" ~ '*{1}' 

For all regions of Russia:
the

select "id", "name" from "world" where "tree" ~ '1.*{1}' 

Examples of the application of this instrument can give a lot. But because of the visibility of this topic, leave it at that.

Opinion

I think ltree — is a great way of organizing tree structures. Through simple and convenient methods of searching and sorting of information, it is suitable for a wide range of tasks.

In this article, I have listed more ltree. Not addressed the issue about indexing, functions, and issues a full-text search ltxtquery. Full documentation can be found at the links below [1, 2].
Actually, PostgreSQL has a lot of additional useful modules [3]. Enjoy reading!

Links

the
1. Description of ltree on a site of the developer
the
2. the Description of ltree in the PostgreSQL website
the
3. Contrib modules PostgreSQL

Article based on information from habrahabr.ru