1/23
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
---|
No study sessions yet.
Tree-Structured Indexing
Uses a tree (usually B+ Tree) to organize index entries for efficient search
B+ Tree
Multi-level balanced tree where all data entries are at the leaf level
B+ Tree Internal Nodes
Contain only search keys and pointers to children
B+ Tree Leaf Nodes
Contain all actual data entries (key + pointer or record)
Order (d) of B+ Tree
Each internal node has between d and 2d keys (d+1 to 2d+1 pointers)
B+ Tree Height
Kept small (log base d of N) to allow fast lookups
B+ Tree Search Complexity
O(log n) where n is the number of entries
B+ Tree Insertion
Insert key at leaf; may cause node to split and propagate up
B+ Tree Deletion
Delete key; may cause merge or redistribution
B+ Tree Range Queries
Supported efficiently via leaf node linked list
Clustered B+ Tree
Data file is sorted in the same order as the B+ Tree index
Unclustered B+ Tree
Data file order differs from index; index points to records
Sparse Index
Points to first record of each page; used with sorted files
Dense Index
Has an index entry for every record
Multi-level Index
Index on top of another index to reduce size and improve performance
Search Key in B+ Tree
Attribute(s) used for sorting and lookup in index
Fan-Out (f)
Number of pointers in an internal B+ Tree node; high fan-out = low height
Overflow Page
Used when too many records have the same search key value
Primary Tree Index
B+ Tree built on primary key (unique, sorted)
Secondary Tree Index
B+ Tree built on non-primary attributes; may have duplicates
Composite Key Index
B+ Tree where key consists of multiple attributes
Advantages of B+ Tree
Supports efficient equality and range queries, updates, and sorted access
Difference from B Tree
B+ Tree stores data only in leaves; B Tree stores data in all nodes