CISC437 Lecture Notes - Lecture 22: Self-Balancing Binary Search Tree, Database

• School: University of Delaware
• Department: Computer and Information Sciences
• Course: CISC437
• Professor: Carterette Benjamin

Document Summary

We are still treating indexes as sequential arrays: inserts are expensive- o(b, updates and deletes can be costly too. Tree index: store index as a balanced, ordered tree. Deepest layer, leaves, is a full index in sorted order. Each parent is a sparse index into its children: insert and delete is o(log n) A b+ tree is a b-tree with key duplication: every key is also stored as a leaf. A b+ tree index is a multi-layer index: leaf nodes contain full index in sorted order, internal nodes are indexes for more indexes, leaf nodes also store pointers to full record on disk. Value of k influences height of tree: influences insert/delete and space. Index height = o(logk/2 n: n = number of keys, can have o(b) extra blocks.