Obsidian + 🪴 Quartz 4.0

DST Lezione 6-7

16 min read

Lezione 6-7

Dynamic Indexing with B-Index and B+-Index

Sources:

  • Lecture
  • Fundamentals of Database Systems - Chapter 17

Search Tree

Let’s consider a range of values:

1,3,5,7,9,10,11,13,15,15

A-node-in-a-search-tree-with-pointers-to-subtrees-below-it

If i consider a binary search tree (each node has at most two childrens) i have a tree that is built upon a threshold that is the same value of the root. If i consider the root value of this tree as (9). then i would get something like this:

			9
		5      13
	3     7  10   15     
1              11

This is an unbalanced tree. But this is not the only possible tree, i may change the root value to 3 and get something like this:

						3
					1      5
								7
									10
										11
											13
												15

On the first tree, at most i may pay to find a value. In the secondo tree i pay either if i want to find a value less than one, or almost surely more than with values higher than three.

B-Tree stands for Balanced Tree.

N-Ary Search Tree

It’s a generalization of the binary search tree. While in the binary search tree, each node as at most two childs. In the N-ary Search Tree, each node has N childs. For example, if N=4 it’s usually called Quad Tree.

To implement an N-Ary Search Tree, i need thresholds. Let’s see with an example why. Consider the previous series of numbers

1,3,5,7,9,10,11,13,15,15

For example, our root values will be (7,10,13). The tree would be like this:

     (7,10,13)
     /   |   \   \
(1,3,5) (9) (11) (15)
  1. The children values in the node at the left of 7 must have a value
  2. The children values in node at the right of 7 and at left of 10 must have value of
  3. Thie children immediately at the right of the previous children would have values between
  4. The children at the far right of this node would have a value of .

So i consider three thresholds.

In average, an N-ary search tree has a cost of to find a value, which is lower than the in the binary search tree.

Balanced Tree and Balanced Index.

The problem of the N-ary search tree is that, with insertion we get overflows in the nodes and we need to reorganize the tree, even adding another level if needed.

To have this structure stable to insertion and deletion, we consider some free spaces in the nodes of the three, say for example atleast 50%. In this way, adding values will not immediatly create an overflow but the structure is somehow more “resilient” to changes.

B-Index are equivalent to B-Trees, they’re the same structure. The difference is that N is called the fan-out of the index. (See DST Lezione 4-5). Also, in a B-Index we have pages instead of nodes.

Balanced Tree:

A tree is balanced if all the leaves are at the same level.

This is the only constraint required. It doesn’t matter if two nodes doesn’t have the same number of childs. On average, the costs to retrieve a page is , with the worst case in the leaves and the best case if the value is in the root.

Definition of a B-Tree Node

Each node in the B-tree is of the form: Where is a tree pointer, while is a data pointer that points to a record.

Warning

For this section you must do exercises and be able to solve them to pass the exam. Here will be just explained the theory with some examples.

Order of the tree

Let be the order of the tree. For calculating this value i need to solve this equation:

Why B/2

By considering 1/2 we are leaving half pages empty to leave free space. This is desiderable to avoid degradation in performance when writing the page (insertion, update, deletion)

Let’s break down each part:

  • First giving a general look, we see that the equation is a sum of two values which must be less than B/2.
  • because as we saw in the previous section, every node has a key. and pointer to a record. Also from definition we got that it got at most keys.
  • because we have pointers to internal nodes at most.

Why and not

We defined a node as: Note that we have more pointers than key, because we also need to consider the last Pointer

Property: The bigger , the better the index

This because the bigger is , the shorter is the tree. The cost of finding a record in a B-Tree is

Calculating order of tree in an heap file, key is unique

How many pointers do i need to address each record? NT → Number of Tuples. My index must be a dense index. How many pages do i need to address each index? →

Height of the tree

Calculating height of the tree in an heap file, key is unique

Size of the tree

This value is the sum of all the nodes from all the levels of the tree.

You cannot simple calculate this with series of powers

Because doing so would be considering that all the nodes have the maximum number of children. This is a very niche and rare case. Also, if you follow this approach you will be wrong in order of magnitudes, it’s not just a small error.

Advantages over static multi level index

As we saw the cost is h/2, so it’s a good situation. Let’s consider the advantage with respect to multi level indexes. In Balanced Trees, the main advantage comes from free space.

For example, say i have to insert a new value in the tree. Since i computed with the constraints that i must be half empty, there is space for other values. I can do insertions before that node is full. When a node is a full, the only nodes that i need to change are: the node himself, his father and his brother. This implies that i only need to change locally the data structure and not reorganizing entirely like i did for hashing. In multi-level index, i need to add overflow and then reorganize the entire index.

To summarize, with Balanced Trees we are getting a tremendous speed up in searches and a very small overhead in writes. We get the best of both searching and writing, thanks to local reorganization of data.

Nota

Devi fare gli esercizi su questa parte

Balanced plus Trees Indexing

It’s a variation of the B-index, called -index.

In a balanced tree, the average cost is h/2, we can be lucky or unlikely, the cost is not costant for all searches. A -Tree is a tree where the cost is always constant. Two things changes with this data structure:

  • All pointers to records are in the leaves
  • The node of each leaf is different from the internal nodes: a pointer to the next (left to right) brother leaf is present in the node.

Definition of a B+ -Tree node

Balanced-plus-tree-example

Internal node: Leaf node: Where the last pointer is the pointer to the brother. With this organization, the last layer of the tree looks like a sorted file.

Order of the tree

  • Internal node:
  • Leaf node: Where is the order of the leaves.

Height of the tree

First, let’s compute the number of leaves.

Then apply the logarithmic formula:

Size of the tree

Da integrare con il libro

(NL/order of internal nodes) = (NP_first level above the leaves)

In real life use cases, the number of leaves is a good approximation of the tree size.

Implication of the B+-Tree and comparison with a B-Tree

In a B+-Tree, the order is bigger, because internal nodes use much less space than the nodes in B-Tree. In fact, in a B-Tree internal nodes have also a pointer to records, while in B+-Tree nodes, only the leaves have these pointers.

In a B+-Tree, the cost to find a value is costant and is , while in B-Tree is on average. It may seem that B-Tree is faster, but the of a -Tree is smaller than the height of the B-Tree.

Another thing to consider is that if you want to search consecutive values, the -Tree is a sorted file where values are in consecutives pages. Yes because, we are considering an index, so each node is a page. In a B-Tree, you have yes leaves on the same level, but consecutive values are not in consecutives pages.

In real life systems, -Tree indexes are the most used

(FACT TO VERIFY)

Also, in real system they sometime break the constraint of all the leaves at the same level just to reduce the I/O operations. But always in a such of way the level of the tree is always three or four

Why not using hashing?

For finding values in consecutive values, the -Tree uses a sorted file where values are in consecutive pages. I do a single search and can find every consecutive values i need. With hashing, the location of data is random, so i need to do independent researches for each value in a range of consecutive values. On average this costs me more than a -Tree.

Others Types of Indexes

Bitmap Indexes

The bitmap index is another popular data structure that facilitates querying on multiple keys. Bitmap indexing is used for relations that contain a large number of rows. It creates an index for one or more columns, and each value or value range in those columns is indexed

A bitmap index is built on one particular value of a particular field. For example, say i have a table of students and one of the fields is “Sex”, which can be usually Male or Female or Others.

Then i create an index based on the ‘M’ value of this field. I would have NT bits, whoose value are one if the correspondent row is a male student, otherwise it’s 0.

The index for every value of the fiels will be:

M: 10010011...NT
F: 01100010...NT
O: 00000000...NT

Cardinality of the bitmap: it’s the number of different values. In our example is three. Total number of bits: → this is the total size of the bitmap Number of pages used by the index: Where B=Block/Page size, NT= number of tuples and is cardinality

After i have keys, i need another data structure whose record are ordered that points to data inside the table.

If i want to retrieve all males, what i should do is:

  1. Read the bit map to find the records which are males
  2. Do a full scan of the auxiliary file to get the pointer to the actual data in the table So the performance depends also con selectivity. for example, If half the students are males, it is not convenient because there is virtually no difference from a linear scan.

Extreme example: Bitmap of an unique key, like the matricola With an unique key, i would get a cardinality of . So the size of my bitmap would be huge: . The cost in terms of pages required by the index would be: , which is huge even for bits.

Advantages

  • Count operations are very convenient because i don’t need to read the data, i just count the s. Alike operations that doesn’t require to access the auxiliary file structure and/or the actual data are convenient.
  • Composite query with logical operators: since these operations can be done at the bitmap level, i just load the bitmap and do complex operation to get only the pointers to the records that matches the condition.

Compression

Another advantage of these bitmaps is that data can be compressed. One very efficient way to do this is to use the Run Length compression, where it is stored the count of subsequent bits that repeats themselves.

Disadvantages in updating

  • Data in the same column of the bitmap is DEPENDENT from each other. So if i update a value like on tuple, then i must also update the values in the same column in the bitmap. At least 2 values must be updated with each update.
M: [1]0010011...NT
F: [0]1100010...NT
O: [0]0000000...NT

If for absurd, student sex of the first student goes for example from M to O, then i have to update both the M bitmap and the O bitmap.
  • If i speed up writing operations with a GPU, it’s easy to get in a deadlock.

The General use case for bitmaps

  • When cardinality is low and you have non unique fields.
  • When you do mostly read operation and update is rare or done in batch. This is the case for example of data analytics, where you never update real time and just want to read.

Logical Indexes

Logical indexes are a special index where the index is composed of a key and the primary key of the data. where =primary key.

For example, in the case of students, if i want a logical index by region i would have:

Cost of searching: assuming a sorted file. This kind of index is dense because region is not unique. So an example index from student table would be:

Where the second value is a list of matricolas.

Size of the index: Is calculated as . In our example the size of the region field plus the size of the matricola field. NRV is number of repreated values and is calculated as: , assuming an equal distribution.

BFR of the index Number of pages of the index:

Cost of retrieving a record: Suppose we have this situation: a logical index auxiliary file, which is sorted points to a field and his primary key. Then say i have another B+-Tree index by matricola. The cost would be calculated as:

  1. Linear scan of the logical index:
  2. Scan of the tree:

So the total cost would be . If i use a multi-layer logical index, the log becomes , different from of the -Tree.

Advantages

  • If data moves often in the physical layer, at the pages level, then i have to completely rebuilt the index. The logical index is unsensitive to this change in memory allocation changes. It doesn’t change

Function based indexes

The idea is to create an index such that the value that results from applying some function on a field or collection becomes the key of the index.

For example, say i have a table of students with birthday, but i want the age. I could create my own age function and using the result from as key

<f(k),p>

The query will exploit the function and i will get a pointer from the age using an existent value and field.

Advantages

  • If i have a complex function that require 1 minute on a field, and i have say 1000 tuples. It would require me 1000 minute each times i want to do this operation. By using this index i would only need to do this one time. And in a reasonable way, rebuild the index periodically.

Inverted indexes

The idea is to have an index that goes from a value to a key. For example, say i have a list of documents, and each one contains a list of words. Say ISBN is the identifier of the documents

D1 -> w1,w2,w3...
D2 -> w7,w1,w4...
D3 -> w9,w2,w1...

What i could do is this: a pointer that for each words lists all the documents ISBNs that contains that word.

Some real life examples:

  • Analytical Indexes in the books: at the end of the books there are a list of words/topics and the page in which they are are mentioned.
  • A search engine: we search words and we get a list of websites that contains that word.

These use cases works too for some kind of structured data, for example in VAR CHAR of variable length field. If our student table has a field “Curriculum” and i want to look for students that have “Java” in their curriculum, using the “LIKE” operator the cost is huge. I have to linear scan the student table and then linear scan all the field looking for the word “Java”. What i could do instead is to build once an index.

Disadvantages

  • With this approach, the problem is if i update the tables, then the index is outdated. Google or any search engine is a well known example of this.

A little note on BLOBs

There is no way to speed up Blob’s retrieval with indexes. Because from a database perspective, it’s just a block of bits that has no meaning. You either retrieve it fully or you don’t retrieve it. It’s not possible for example to search inside the BLOB.

Usually, the primary key of the table is associated to the BLOB.

Graph View

Backlinks