Month: May 2022

A binary search tree is a data sorted structure where each record can be linked with a máximum of two other records. We are going to pay special attention to binary search trees, as they are very popular and widely used in databases. As I anticipated in the previous post, binary trees are of order 2, that is, each node can have a maximum of two children. Additionally, for being a search tree, all nodes have to meet the following conditions:

• if the node has a left child, the value of it has to be smaller than the value of the father.
• if the node has a right child, the value of it has to be higher than the value of the father.

This forces that the data we are saving are sortable, so we can determine if one is bigger or smaller than another. Given the conditions above that a binary search tree has to meet, duplicates are not allowed, they have to be unique data.

Let’s look at it with a simple example where data are integers. The binary search tree for our example is:

Continue reading Binary search trees

In the indexed files seen in previous posts, the table of indexes is accessed sequentially with the drawbacks that I already mentioned this type of access has. However, there is a much more efficient indexing technique than sequential indexing and that is tree indexing, which significantly reduces search time. In this post, I will explain the aforementioned technique.

Using sequential access, when looking for data, it has to go through the index file sequentially until we find the searched one, obtaining the memory address of the beginning of the record in the data file. As index tables are much less heavy than files with all the data, we have a considerable improvement using indexes, even if the search in the table for these is sequential.

By changing the index table of sequential access to an organization of the indexes in a data tree, it will be able to access the indexes much more quickly. These types of structures are specially indicated to speed up searches, but let’s see how it does.

Continue reading Tree indexing