Indexes

Question 1

What does B-tree index mean? How does it work?

Answer 1

Balanced search tree. These tree contains of root node branch node and leaf node. Branch node contains the biggest number (id) from each leaf node. The B-tree enables the database to find a leaf node quickly. ( because tree deep is equal and quite low (3-4)

Question 2

Where do we store db data on the system level?

Answer 2

In mysql we store data in the files with special extention.

Question 3

Where do we store indexes on the system level?

Answer 3

In index leaf nodes which are stored in a database block or page; that is, the database’s smallest storage unit.

Each leaf nodes connect with each other using a double-linked list ( this list are sorted).
Each leaf node contains several rows with (id and link to the main object ( its physical place) ).

Question 4

What is db index? Why do we need it?

Answer 4

Data structure that DB use to find row fast.

Question 5

How does index connect with indexed data?

Answer 5

-

Question 6

What is a clustered index?

Answer 6

Contains the index and row itself.

Question 7

How does db index work inside? Why do we think that it can help us improve performance?

Answer 7

Searching in a database index is like searching in a printed telephone directory. The key concept is that all entries are arranged in a well-defined order. Finding data in an ordered data set is fast and easy because the sort
order determines each entries position.

We can think about indexes as 2 Excel file ( one to store the whole data, the second to store only all sorted ID inside 2 columns -> id, and link to the cell of the main file (A1,B10,GH123) )

Question 8

What is index leaf node?

Answer 8

It’s the smallest block where we store index.

Question 9

What is a balanced tree?

Answer 9

The structure is a balanced search tree because the tree depth is equal at every position; the distance between root node and leaf nodes is the same everywhere. A balanced tree is a tree where every leaf is on the same distance away from the root than any other leaf

Question 10

When index doesn’t improve performance?

Answer 10

1) When we have too many not unique records
2) The fewer indexes a table has, the better the insert, delete and update performance.
3) When amount of records are small
4) Concatenated index if we searching not but the left column

Question 11

How balanced tree works if data is equal?

Answer 11

As all leaves are sorted we need to check if we don’t have the same item near.

Question 12

What steps need to be done to finish the index search?

Answer 12

An index lookup requires three steps:

1) the tree traversal;
(2) following the leaf node chain; ( if equal items for example
(3) fetching the table data.

Question 13

What is concatenated/composite index?

Answer 13

Index which is created on several fields. (also known as multi-column, composite or combined index).

Note that the column order of a concatenated index has great impact on its usability so it must be chosen carefully.The database considers each column according
to its position in the index definition to sort the index entries. The first column is the primary sort criterion and the second column determines the order only if two entries have the same value in the first column and so on.

If we are searching by only the second of the concatenated indexes columns the result will be as we don’t have an index at all.( but for the first one is works)

Question 14

What is function-based index (FBI)?

Answer 14

An index whose definition contains functions or expressions is a so-called function-based index (FBI). Instead of copying the column data directly into
the index, a function-based index applies the function first and puts the result into the index.

( For example CREATE INDEX emp_up_name
ON employees (UPPER(last_name)); )

Question 15

What is deterministic function?

Answer 15

A deterministic function always returns the same result for the same input parameters whereas a non-deterministic function returns different results for the same input parameters. ( something like clear function)

Question 16

How would be better to start search by equality? or by range ?

Answer 16

index for equality first—then for ranges.

Question 17

What is full-text index?

Answer 17

This is an index for full-text search ( for example using LIKE operation for filtering).
Very simplified: They split the text into words and make an index over the words and not the whole text. This works a lot faster for text searches when looking for specific words. ( This kind of index work as search engine and tries to find keyword)
To realize it we use 2 steps b-tree ( first step by keyword, the second by the string itself)

• We select keywords
• We remove stopwords
• We remove words that we use more than (50 % cases)

Question 18

Is it better to create one index for each column or a single index for all columns?

Answer 18

The answer is very simple in most cases: one index with multiple columns is better.

Question 19

What is filter predicates?

Answer 19

-

Question 20

What is bitmap index?

Answer 20

The bitmap structures are not stored persistently but

discarded after statement execution, thus bypassing the problem of the poor write scalability.

Question 21

What is partial indexes?

Answer 21

The index only contains the rows that satisfy the where clause. ( for example only for the row which includes specific type )

Question 22

What is a covering index?

Answer 22

A covering index is an index that “covers” a query. That is it supplies all information for the query so that SQL Server does not have to touch the base tables. ( Index already contains all information that you need )

When you create an index on T (col1, col2), you have a composite index because the index consists of 2 columns.

Suppose now you have a query like:

SELECT col1, col2
FROM T
WHERE col1 = something AND col2 = something else

For such a query the newly created index could act as covering index, because SQL Server can satisfy the query by just touching the index.

Question 23

What will be work better: index on column that allows NULL or NOT NULL columns?

Answer 23

• NOT NULL columns, try to set not_not if you’re going to add an index on this field.

Question 24

What is hash index?

Answer 24

Hash indexes use a form of the hash table data structure. We convert column data with hash function and store value by uniq key.

Question 25

What is a prefixed index?

Answer 25

This index allows to index only part of the column value ( For example one first 10 characters)

Question 26

How to select what field should be first for concatenated indexes?

Answer 26

For example we have stuff_id and company_id. We need to find how many uniq records we have for each row with these values and select as the first one most uniq.

Question 27

What is SSTable?

Answer 27

Sorter string table ( everything is sorten by key )

Question 28

What is LSM tree?

Answer 28

A log-structured merge-tree (LSM tree)

• Writes are stored in an in-memory tree (also known as a memtable).
• When this tree becomes too large it is flushed to disk (segments ) with the keys in sorted order.
• When we read we check memory then disk

Question 29

What is Spatial Index?

Answer 29

(пространственные индекс) You can use a spatial index for indexing geo-objects - shapes. The spatial index makes it possible to efficiently search for objects that overlap in space. Uses R-tree indexes for realizations.

Question 30

What is R-tree index?

Answer 30

The R-tree enables you to index multidimensional objects.

Question 31

What Does Fuzzy Search Mean?

Answer 31

A fuzzy search searches for text that matches a term closely instead of exactly. Fuzzy searches help you find relevant results even when the search terms are misspelled.