Databases: Tree Indexes

 A bunch of people finished, and post of piazza, and we get pin posts on piazza.

Recall from last class, we started talking about the different data structures that we have, especially Hash Tables, using it for internal metadata, underlying table, temporary data structures, etc. 

Table indexes are queries that will do range scans, and hash tables will be useless in this case.  

The database system helps to keep the indexes completely synchronized with the table. 

A table index is a replica of a subset of attributes of the table, to do efficient lookups to find the thing that we're looking for. Examples are looking for a particular key in the table, among other potential things. The index is going to be a replica of the table, meaning that it has to be synchronized with the table.

There's a tradeoff between having lots of indexes and the cost of maintaining these indexes. The database is responsible for figuring out what is the most efficient method. It is the DBMS's job to figure out the best indexes to execute each query. There is a tradeoff on the number of indexes. When I do updates to the table, this means I also have to update all of the indexes to reflect those changes. The update operation isn't considered done until I modify all the indexes and synchronize all of them. 

So today's thing will be about B trees and the implementation details and concerns and additional optimizations that real systems do. A B-Tree is sort of a balanced tree data structure. There is a class of data structure and within there is a specific data structure called a B-Tree. 

A B+ tree is a self-balancing tree data structure and it keeps data we insert in sorted order which allows us to do efficient searches, access, insertions and deletions. We allow this to happen O(log n) since the B+ tree is balanced. 

B+ tree came out in the 1970s because they tried to do indexing.B+ tree can scan across the leaf nodes and read everything in sequential order. In general, it's still widely used today even in disks, and the B+ tree outperforms a lot of things. 

There's no paper describing what the B+ tree is. We're going to borrow bits and pieces from a lot of other trees, and we can technically call it a B+ tree. 

B+ tree is a self-balancing tree data structure with log n time. B+ tree is an M-way search tree within every node with M differenty paths to other nodes, perfectly balanced and every node other than the root is at least half full. If i'm not half full, we move data around until a certain node is half full. If a node has k keys, this node has k + 1 non-null children. 

Along the bottom of the B+ tree, we have a leaf node and any node that is not a leaf node is considered an inner node. Then the leaf nodes have sibling pointers, and any inner node won't have sibling pointers, but any leaf node will. Keys are then used to determine which path to go down as you start to search for a given key. It goes like <node*> | <key>. At the bottom, it's noted by <value> | <key> .

The keys in each node are always sorted in sorting order corresponding to each node. We can do binary search rather than just having to do a linear search. 

There can also be a level number slots, previous next, sorted keys, and values. 

The original B-Tree from 1972 stored keys and values in all the nodes in the true, but B+ trees only store the values inside of the leaf nodes. I am basically duplicating keys in the node. A B tree is going to be more economical, since it's not duplicating keys. However, it makes updates more expensive when you have multiple threads. I only make changes to the leaf nodes in the B+ tree. Key 5 for above tree is not in the leaf node, since it won't show in the actual leaf tree (5 is the parent). We want to traverse down and figure what leaf node we want to insert the key into and we will get to the leaf node and then the leaf node is where wae want to insert the key. 

You can have keys with nonunique values. First we want to find the correct leaf node L, put data entry in sorted order. We are done if L has enough space, otherwise, split L keys into L and a new node L2. To split inner node, redistribute entries evenly, but push up the middle key. As I keep inserting more stuff to the B tree, I keep splitting the changes up as a result. Duplicate keys won't really matter. Push the middle key up to the top.

Now, let's go over the B Tree Deletion. Start at root, and then we find where the entry belongs, we remove the entry. If L is at least half full, then we're done.  If the leaf node has M/2 - 1 entries, we try to redistribute borrowing from sibling otherwise we just merge the L and the sibling and delete the entry from the parent of L. 

We want to make sure that we're thread safe and no integrity issues when reorganizing the trees.

The amount of data stored in the node, around 67% is useful data.

We can define a cluster index and the data system will guarantee the physical layer of tuples will match the order they are sorted in in the index. 
The table is stored in the sort order specified by the primary key, and it can be either heap or index-organized storage, and some DBMS's always use the clustered index, others cannot use them at all. 

The DBMS can use a B+ tree index if the query provides any attributes of the search key. For the hash index, we must have all attributes in the search key. An example is index on <A, B, C>. Everyone suppports the prefix, not everyone can do the middle one. 

Let's do a prefix search where I only do the first composite of a particular key. 

Find Key = (A, *) is easy since we go through those keys in sequential order. 

We substitute different values for the thing that I don't have and substitute the star with an A, with a B, then with a C, this is called skip-scans.

No we know what a B+ tree is now. 

There are certain rules for the B trees. 

Let's denote some rules for a b tree of 

1. A node can have a maximum of m children.

2. A node can contain a maximum of m - 1 keys. 

3. A node should have a minimum of ⌈m/2⌉ children. A node should also should contain minimum of ⌈m/2⌉ - 1 keys.

Here's after the replacement:

And here's what happens if we delete an internal node: 

If the deletion of a key violates the property of minimum number of keys a node should hold, we should borrow a key from the neighboring sibling node in the order of left to right. The deletion of a key may violate the property of the minimum number of keys that one should hold. We first visit the immediate left sibling and if the left sibling has more than the minimum keys, borrow from this node, otherwise, borrow from the right node. 

Modern B-Tree Techniques by Goetz Graefe is a good book for this. 

In practice, you need to have a larger node size or smaller node size. The slower the disk you have, the larger the node size you want. For every Disk IO, I can read the node sequentially and that can be very fast than if the node is a smaller size. Optimal sizes can vary depending on the workload. The next thing is we have to violate the thing at the very beginning. Merging operation and splits are expensive. However, we can relax things and not merge right way and have a garbage collector once in a while and do rebalancing. 

There are 4 different ways of storing keys. 

1. store a pointer to a tuple

2. variable length node: the sides of each node in the index can vary, but this requires careful memory management.

3. Padding: Always pad the key to be max length of the key type. We want the page size to be always the same on the buffer pool or the disk. 

4. Key Map / Indirection: Embed an array of pointers that map to the key value list within node. We define a varchar when we call create table. 

MYSQL has an issue with VARCHAR that it will just truncate if you have longer than the size of the varchar. Just a fun fact. 

What's more common is to use an indirection map where we'll store pointer as 2 offsets of the node themselves, rather than some arbitrary page. 

The other thing people ask about is how to handle non-unique indexes. 

1. Duplicate the keys, and be mindful this can occur. We split these keys into another node. 

2. Store a value list, store the key once, separate space for values for certain key. 

The offset points down to wherever the value is, and sort and move everything over. The value list is storing the key once, but offset in the node where I have all the values that correspond to a given key. 

We can first scan node keys from the beginning to the end. Otherwise approach 2 is binary, jumping to the middle key, pivoting left/right depending on comparison. The third attempt we can do is interpolation, where we approximate location of desired key based on the known distribution of the keys. We can compute the offset to the nth position, and compute at least the STARTING point we are able to begin at. 

Problem with binary search is that we have to do sort order. 

The newer keys might get stored in one side of the tree, and there are a lot of tradeoffs. 

If we insert "sad" we have to remove the prefix, etc.

The opposite is suffix truncation, recognizing that we don't need the entire key of the inner node.

They keys in the inner nodes are only used to "direct traffic" when we don't need the inner key. We store a minimum prefix that is needed to correctly route probes into the index. Again, we don't need the entire key. 

Down below, I need to store the entire key, but inner guidepost doesn't need the whole key. We store a minimum prefix used to correctly route probes to the index. 

We assume that we're incrementally building out our index, and inserting the keys one by one. A really simple optimization to build the index is to build things from the bottom up. We first sort the key data and then lay it out around leaf nodes, and then fill in the inner nodes and generate our pointers. It generates the children first, then it will generate the parents. 

The last thing I want to talk about is pointer swizzling. We're storing page id's and nodes use page ids to reference other nodes in the index, where the DBMS must get memory location from the page table during the traversal. Then we can get a pointer to pages and I want to get to sibling, which is page 3, and then we go down to the node, respectively. When I do traversals, I might do page pointers instead since I don't have to ask the buffer pool, but we don't blow away the page id entirely (deletion issues) but we denote the pointer for the page id right away. The page refers to the blue rectangles. 

B+ tree is always good for Database Management Systems. The next class will show additional optimizations.