Today in database management systems there is an acute problem of searching for data in large data sets. To solve this problem, we propose a modified search tree and its improvement using a fractal index search tree with a multilevel structure. Each level in such a structure is a separate fractal tree. Algorithms for data processing in DBMS RAM by modified methods are described. These methods can be used to search for the same data from different tables. Increased the minimum filling of the node, which reduces the height of the tree. The symmetry of the fractal tree helps to execute the query quickly and, as a result, reduce the number of requests to the disk subsystem. Also, due to the self-similarity property, the most frequently used indexes will be loaded into the DBMS RAM much faster after selection. This will speed up the process of finding the information you need for the request. Loading data indexes into RAM based on statistics on the frequency of use of indices and index size weights will reduce the number of indexes that are loaded into RAM, in contrast to the classic loading where the loading of indexes occurs during their use and after filling the memory, it is deleted. Another big advantage is that indexes that are almost never used will not be loaded into RAM. The proposed approach with fractal trees also has an important scaling property, as fractal trees are divided into a large number of smaller trees, which is especially true in the era of multicore modern computer systems. To study the effectiveness of the use of indexes based on a modified fractal search tree in the database and select the best system for hosting the database server, we measured the speed of information retrieval in tables for the Windows 10 operating system. During the experiments it was shown that the search speed on the modified trees in comparison with the modified fractal search tree is reduced by 12%.
In today's world we can see a rapid increase in
information, which complicates the process of its
storage and management. Therefore, for its
organization and quick search using databases
(DB), which are organized according to the
concept that describes the characteristics of this
data. In modern information systems for
highquality work with databases use DBMS database
management systems that provide the ability to
create, store, update and search for the necessary
information. DBMSs also provide a number of
useful services: schema to control data semantics,
query language to organize access to part of the
database, data granulation, data integrity
management, compression to reduce database
size, indexing to speed up query processing.
However, the integration of different databases
into the production process at enterprises and
other institutions has a number of shortcomings
associated with the organization of their
management and monitoring of events in
databases [
In modern databases, an important element is
the search for data in tables that contain many
rows and columns and are not always ordered.
Therefore, to implement a quick search, indexes
are created that are formed from the values of one
or more columns and pointers to the
corresponding rows. Indexes allow you to avoid
sequential or step-by-step browsing of the file in
search of the desired data. They are ordered, each
element of the index contains the name of the
searched object and a pointer-identifier of its
location. The more indexes, the better the
performance of database queries, but a very large
number of indexes does not guarantee high
performance [
Many databases use different trees and their modifications to build such indexes. However, if the tree has an insufficient number of nodes and their fullness, the data search time increases [1113]. The disadvantages may also be the use of identical indexes for different tables and sending to the RAM of indexes that are rarely used [1415].
The base trees in index construction and data
retrieval are B-trees, namely their type B + trees.
These trees easily implement the independence of
the program from the structure of the information
record, have the ability to sequential access and
all key data are contained only in the sheets. The
main disadvantages of such trees are the
compactness of filling and the number of levels of
trees [
You can also select K-trees, which contain all
the characteristics of the B + tree, but have a better
strategy of splitting and merging nodes. Also,
these trees have more elements at the root of the
node and the fullness of the node is ¾. All this
saves hard disk space and increases the speed of
access to information [
However, the index structures used in modern databases have some limitations due to the long process of restructuring the index structure in the case of adding or removing new data. Accordingly, this leads to a slow process of searching for information in a database with large data sets.
The aim of the article is to improve the process of processing indexes in databases using fractal trees and speed up query execution.
The existing mechanisms of data modification
in the tables have a certain feature - the change of
keys in the corresponding nodes of the tree is
performed with the subsequent restructuring of
the index. This significantly affects the speed of
writing information to the database and,
accordingly, is an important factor in increasing
the number of queries to the database. You also
need to store only the most frequently used
indexes, then, accordingly, the access time to the
data storage location will be reduced. Therefore,
the existing methods need to be improved, which
will allow to find the necessary information faster
[
In the + tree we will improve as follows: • increase the minimum filling of the node, which will reduce the height of the tree; • change the rule of separating the nodes of the tree - splitting the node with its two neighbors into four new nodes; • change the rule of connecting tree nodes connecting four nodes into three new nodes; • in the tree leaf we will store records of links to the same fields in different tables, which will increase the time of receipt of links to data in the tree and speed up the search.
We describe the search for data using indexes. Indexes are loaded into the RAM of the database after receiving the request. Next, a list of data is formed, which contains the necessary information, and the found data is sent to RAM. However, in the classical algorithm for loading indexes in the RAM are indexes that are almost not used, and, accordingly, take place until they are replaced by other indexes. Therefore, it is necessary to improve the procedure for processing indexes in the RAM of the database (Picture 1) by: • reducing the specific storage in the RAM of indexes that are little used; • processing little-used indexes by reading them from disk.
Collection of statistics on the use of indices
Loading indexes in
DBMS RAM
Change of indices for the new period
Here is an algorithm for loading indexes into memory based on the index hashing method: • DBMS loads indexes into RAM according to the classical algorithm and collects statistics on the number of used indices during ∆t; • after collecting statistics, the DBMS loads into RAM only those data that were used most often during the time period ∆t; • if there is no data in the RAM during the query, the search is performed by reading nodes from the disk index space of the database; • if the time ∆t has expired, then in RAM are loaded those indexes that are used most often and have not been loaded before.
This algorithm is implemented in two stages: 1. statistics are collected on the number of used indices for the corresponding period ∆t; 2. the indices that were most often used in the previous time interval ∆t are loaded into RAM.
We have a formula for calculating time: ∆ = (∑ =1 ) (∑ =1 ) , (1) where – the number of used i-th index, – the number of indexes used, – the weighting factor of the i-th index, – time of statistics collection.
Loading data indexes into RAM (figure 1) based on statistics on the frequency of use of indices and index size weights leads to a decrease in the number of indexes that are loaded into RAM, in contrast to the classic loading, where the loading of indexes occurs during their use, and after filling the memory, it is deleted. Another big advantage is that indexes that are almost never used will not be loaded into RAM.
Recently, fractals are increasingly being used in various areas of our lives. Fractals can be used to model and describe various phenomena in the fields of radio engineering and electronics, digital information processing, and computer graphics [23].
The concept of «fractal» was proposed by the French-American mathematician Benoit Mandelbrot. In 1977, he published Fractal Geometry of Nature, describing repetitive drawings from everyday life. According to him, many geometric shapes consist of smaller shapes, which when enlarged accurately repeat a large shape. After research, he also found that fractals have chaotic behavior, fractional infinite dimension and can be described mathematically using simple algorithms.
Fractal in a more general sense means an irregular, self-similar structure, set, subsets and elements of which are similar to the set itself. Fractals can be deterministic or stochastic. They can also be classified according to self-similarity. There are three types of self-similarity in fractals: exact self-similarity (looks the same at different magnifications); almost self-similarity (fractal looks approximately (but not exactly) self-similar at different magnifications); statistical selfsimilarity (fractal has numerical or statistical measures that persist with magnification). Examples of fractals are the Cantor set, the Lyapunov fractal, the Serpinsky triangle, the Serpinsky carpet, the Menger sponge, the Apollonia grid, the dragon curve, and the Koch curve. Also recently, attention is paid to fractal trees: from each branch depart smaller, similar to it, from them - even smaller (figure 2). By a separate branch of mathematical methods can describe the properties of the whole tree.
To construct the structure of the indices will be used Pythagorean fractal tree - a flat fractal, consisting of interconnected right triangles of squares built on the legs and hypotenuse (figure 3).
The Pythagorean tree with N levels is a trunk and two Pythagorean trees with N-1 levels depart from it symmetrically, so that the length of their trunks is 2 times less and the angle between them is 90 degrees (figure 4).
The Pythagorean tree is divided into subtree blocks, where each tree is a full-fledged fractal tree. We present this subtree in the form of a new horizontal level, which complements the vertical structure of the original tree. If the new horizontal level is too large, then in order to fit into one block of the disk, it is divided into two blocks and indexed in the third horizontal level.
These indexes can be easily used for large databases. The structure of such indexes is presented in the form of arrays with a length equal to powers of number 2. This structure is easily scalable for a large number of keys, and is not sensitive to the content of the entered queries.
The main advantage of using fractal trees is that the resulting structure is symmetrical and internally balanced. Symmetry helps to execute the request quickly and, as a result, there will be much fewer requests to the disk subsystem. Also, due to the self-similarity property, the most frequently used indexes will be loaded into the DBMS RAM much faster after selection. This will speed up the process of finding the information you need for the request.
The index uses a new multi-level approach additional levels of the tree allow you to search in the data block that contains the information on request. Each request accesses the same number of levels, which provides balanced access to the index and disk subsystem.
Updating, inserting and deleting indexes can be done very efficiently. The update is performed as a sequential deletion of the old key, followed by the insertion of a new key value. Inserting a key into a fractal tree involves adding one new node or adding an edge to an existing node. Inserting requires changes to only one block at level 1. First, look for a block to update - if the block is crowded, it must be divided, and this leads to the creation of a new node in level 2. Separation of blocks is very rare and does not affect performance.
To study the effectiveness of indexes based on a modified fractal search tree in the database and choose the best system for hosting the database server, we measured the speed of information retrieval in tables for Windows 10. Experiments show that the search speed of modified trees compared to modified fractal search tree is reduced by 12% (Picture 5).
The average error of the result for the modified search tree is 0.91%, and for the modified fractal search tree is 0.89%. Therefore, the experiments are performed correctly and provide the results with a given accuracy.
В+-tree
Modified fractal tree
New methods of index processing in databases for speeding up information processing are offered. The developed modified methods differ from the known methods of processing queries in databases in that they can be used for a large amount of information. Loading data indices into RAM based on statistics on the frequency of use of indices and index size weights leads to a decrease in the number of indexes that are loaded into RAM. A modification of the data processing algorithm in RAM has been performed, which has made it possible to exclude indexes that are rarely used in memory. The resulting structure is balanced and optimized for storage in the disk subsystem, reduces the number of I / O operations to a minimum. The method of constructing indexes based on a modified fractal tree allows to increase the data search speed by 12% compared to the modified method of index search based on a classic B + tree. The proposed approach also has an important property of scaling, as fractal trees are divided into a large number of smaller trees, which is especially true in the era of multicore modern computer systems.
Prospects for further research are seen in the creation of new methods for processing queries in distributed databases based on index hashing using fractal trees.