Notes@HKU by Jax

Indexes

Motivation

Primary & secondary indicies

B+ trees

Structure

"Holds maximum of kk keys": create B+ tree with order m=k+1m=k+1.

Key restrictions:

  • A leaf node must hold ⌈(k)/2⌉\lceil (k)/2 \rceil to kk keys
  • A non-leaf node must hold ⌈(m)/2⌉\lceil (m)/2 \rceil to mm pointers

Balanced tree:

  • All data are stored in the leaf nodes (tree is always balanced), which are linked together to form a linked list.
  • The search time is always O(log⁡n)O(\log n), where nn is the number of keys in the tree.

Operations

Traversal

To search for a key, we start at the root node and traverse down the tree, following the appropriate child pointers based on the key values until we reach a leaf node. The leaf node is then searched for the desired key.

Insertion

When inserting a new key, the tree is traversed from the root to the appropriate leaf node. If the leaf node is full (overflow), it is split into two nodes, and the middle key (right of divider) is promoted to the parent node.

Consider k=3k=3:

    [3,5,10]
    /  |  |  \
[1,2]->[3,4]->[5,6,7]->[10,11,12]

To insert 99:

Step 1:
    [3,5,10]
    /  |  |  \
[1,2]->[3,4]->[5,6,7,9]->[10,11,12]
                ^ overflow keys > k
 
Step 2:
    [3,     5,     7,     10] < promoted 7 after dividing, overflow keys > k
    /  |     \      \     \
[1,2]->[3,4]->[5,6]->[7,9]->[10,11,12]
 
Step 3:
          [    7    ] < promoted 7 after dividing
         /         \
       [3, 5]        [   10   ]
      /  |   \        |    \
[1,2]->[3,4]->[5,6]->[7,9]->[10,11,12]

Deletion

When deleting a key, the tree is traversed from the root to the appropriate leaf node. If the leaf node becomes too empty (underflow), it is merged with a sibling node, and the parent node is updated accordingly by removing the key that separated the two nodes.

Consider k=3k=3:

                    [   9   ]
                    /        \
      [ 3     5     7]       [   11   ]
      /   |   |     \        /      \
[1,2]->[3,4]->[5,6]->[7,8]->[9,10]->[11,12]

To delete 1212:

                        [   9   ]
                    /        \
      [ 3     5     7]       [   11   ]
      /   |   |     \        /      \
[1,2]->[3,4]->[5,6]->[7,8]->[9,10]->[11] < underflow keys < k/2
 
                        [   9   ]
                    /        \
      [ 3     5     7]       [      ]
      /   |   |     \           |      < underflow of pointers < m/2
[1,2]->[3,4]->[5,6]->[7,8]->[9,10,11]
 
      [ 3     5     7        9] 
      /   |   |     \       \  < overflow of pointers > m
[1,2]->[3,4]->[5,6]->[7,8]->[9,10,11]
 
               [7] < promoted 7 after dividing
             /      \
      [ 3,5 ]         [ 9 ]
      /   |  \      /      \ 
[1,2]->[3,4]->[5,6]->[7,8]->[9,10,11]

Observations

TBC...

Static hashing

Bucket

  • Contains one or more records.
  • Records with different search-key values may be mapped to the same bucket; thus entire bucket has to be searched sequentially to locate a record.

Hash file organization: Obtain the bucket of a record directly from its search-key value using a hash function.

Hash function

hh: a function from set of all possible search-key values to a set of bucket addresses {0,1,…,N−1}\{0, 1, \ldots, N-1\}, where NN is the number of buckets in the file.

TBC...

On this page