How to apply search trees in real projects?

Question

Database

I study in absentia, at the last session they introduced the subject of SAOD, talked about trees, lists, stacks. If everything is clear with the latter, then everything is not so simple with trees.

So, we were given an introductory course, given a training manual and a couple of labs, everything was handed over and at the end they were given a coursework: we need to make a small database (sorting, searching), using the acquired knowledge to the maximum. But here's the problem: they explained everything to us in numbers, but I have few ideas on how to apply this in a real project. How to use a tree to store and retrieve the same strings? What will be the keys, how to determine the weight in this case?

Tell me where to read about it? All I find are lectures from different universities, which, like my training manual, only give a superficial idea ...

Answer 1

Search trees are good because they allow you to quickly perform all the basic operations: search, insertion, deletion. There are many different trees: AVL , red-black , various variations of B-trees and many others .
If we store some related data in the database (i.e., records consisting of several values, possibly of different types), then we can select one of these values ​​(which more or less uniquely characterizes the record, or we will often refer to to this entry by this value) as a key. Thus, knowing the key, the user of our database will be able to quickly get all the data associated with it.
I won’t tell you the details of the database architecture and the structures used (and they probably use the achievements of science that are not covered in university courses), but I can say the following:

• If your base is small, use a red-black tree (or AVL).
• If the base can be large, use B trees (for cases where all the data simply does not fit into memory).

In each node of the tree, you will store in addition to the key, references to children and, possibly, some auxiliary information for balancing, also those additional values ​​that can be associated with the key.
The type of the key, of course, is completely unimportant. The main thing is the ability to compare keys and determine which of the two is less / greater.
However, I would not really call such an application a real project. In real projects, you rarely have to manually implement any data structure - you can always (and should) use existing libraries.

Answer 2

en.wikipedia.org/wiki/B-Tree
has a picture there, it explains everything. or look for b-tree or database index in Russian.

Answer 3

Buy Cormen, you won't regret it.
www.ozon.ru/context/detail/id/2429691/

Answer 4

In fact, trees are used not only for strings, for example, in geometry, you often can’t get anywhere without them. Look at kd-tree for nearest points or octree for volume representation.

Answer 5

So you are looking not by rows but by tree indexes. Usually in labs this is implied, and not full-text search.