DATA3404 Lecture Notes - Lecture 3: Candidate Key, Table Table, Unique Key

• School: University of Sydney
• Department: Data Science
• Course: DATA3404
• Professor: Uwe Roehm

Document Summary

Index consists of: location mechanism (directing search) Index entries (either containing data records or pointers to them) If index entries contain actual records (rows), called integrated index. Leaf nodes form a double-linked list: the entries in each node are sorted; for all separator entries (ki ,pi ) holds: " k subtree(pi ): ki k < ki+1. Notes: this means that all nodes (except the root) are at least half full, the average number f of children per node is also called fanout (typically >100) In case of overflow, node splits into two, dividing elements such that both nodes are at least half-full. Finding all records with a search-key value of k: start with the root node, examine the node for the smallest search-key >= k, otherwise k kn 1, where there are n pointers in the node. If such a value exists, assume it is ki .