Little about trees

Introduction

Have you encountered a situation when you need to implement storage of a tree structure in a relational database?



Examples are many. These are tree-like comments, a product catalog, and populated areas divided by countries and regions. I think that everyone will be able to give some examples on their own.
')
In this topic, we'll talk about one of those opportunities that exist for storing trees in PostgreSQL - ltree .

Installation

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

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

Short description

ltree allows you to store tree structures in the form of tags , as well as provides ample opportunities to search for them. [12].

The label can consist of letters of the Latin alphabet, numbers and underscores. You can make paths from labels, which are stored in ltree.

The path of labels is a collection of 0 or more labels separated by dots. For searching by paths, special queries are used - lquery .

Examples of lquery:

1. foo - entries with a label path exactly equal to foo;
2. foo. * - records whose label path starts with foo;
3. * .foo. * - any entries whose path labels contain foo.

Lquery modifiers:

1. * {n} - the path contains exactly n labels;
2. * {n,} - the path contains at least n labels;
3. * {n, m} - the path contains from n to m labels;
4. * {, m} - the path contains no more than m labels.

In addition, there are modifiers for tags:

1. foo * - any label starting with foo;
2. foo @ is a case-insensitive label, for example: Foo, FOO, FoO will do;
3. foo% - selects foo_bar, but does not select foo and foobar.

Modifiers can be combined.

ltree can be compared with each other and c lquery, i.e. standard comparison operations =, <>,>, <,> =, <= are fully supported. In addition to them, several more operations are introduced:

1. ltree @> ltree - whether the left member of the expression is an ancestor of the right;
2. ltree <@ ltree - whether the left term of the expression is a descendant of the right one;
3. ltree ~ lquery or lquery ~ ltree - whether ltree matches the query in lquery.

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

Usage example

We learned a little about trees. Let's try to implement by example.

Our task is to implement the storage of territorial units in the form: country - region - city.

Create a table:

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

Fill the data:

  id | name | tree ----+----------------+------- 1 |  | 1 2 |  | 2 3 |  | 3 4 |  | 1.4 5 |  | 1.4.5 6 |  | 1.4.6 

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

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

For all regions of Russia:

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

There are many examples of this tool. But due to the visibility of this topic, we dwell on it.

Conclusion

It seems to me that ltree is a great way to organize tree structures. Thanks to simple and convenient methods of searching and sorting information, it is suitable for a wide range of tasks.

In this article, I have listed far from all the possibilities of ltree. The question of indexing, functions, and ltxtquery full-text search questions was not addressed at all. Full documentation can be found at the links below [1, 2].

In general, PostgreSQL has many additional useful modules [3]. Enjoy learning!

Links

1. Description ltree on the developer's site
2. PostgreSQL ltree description
3. PostgreSQL contrib modules