Index & B+ tree

Index

An index is a data structure that speeds up selections on the search key field(s)

Search key：any subset of the fields of a relation
the search key is not the same as the key(minimal set of fields that uniquely identify a record in a relation).

Entries in an index: (k, r)
k: search key
r: records or record ids

Index分类：

• Clustered index
  • records sorted & stored in the order of search key
  • row data is stored with the key, so that's why the entry is (key, record) in index
  • For MySQL database, it automatically creates a clustered index for
    1. primary key if exists;
    2. if no pk, they create a clustered index for 1st unique key;
    3. if no pk and unique key, they use row ID (this is a hidden attribute for MySQL)
• unclustered index:
  • records are not sorted in key order

search key 分类：

• unique search key
• composite search key: a list of fields

for different queries, the index can be useful or useless

index performance.png

B+ tree

B+ tree is a data structure that helps search data, it is often used in DBMS or file system

• Search Tree
• in the disk, often makes 1 node = 1 block
• there is a parameter called d in the B+ tree

结构：

root, internal node, leaf node

• root has [1,2d] keys
• each internal node and leaf node has [d,2d] keys
• each leaf node connects to its next sibling by the end pointer, so leaves are like a linked list. which supports range query efficiently

Before splitting for a leaf node.png

After split, 5 keys and 7 pointers

After splitting for a leaf node.png

Before splitting an internal node, there are 5 keys and 6 pointers;
After splitting, there are still 5 keys and 6 pointers

spliiting an internal node.png

Insertion cascaded:
splitting a leaf node may lead to splitting of its parent and ancestors.

B+ tree 上index的删除

Deletion is the opposite operation of insertion
risk: underflow
strategy: merging

-If a node is below the min capacity after deletion， which is producing underflow, try the following in the given order

1. move a key from an immediate left sibling;
2. move a key from an immediate right sibling;
3. merge with an immediate left sibling;
4. merge with an immediate right sibling