Tutorial 1.0

B+ Tree and Hashing B+ Tree Properties B+ Tree Searching B+ Tree Insertion B+ Tree Deletion Static Hashing Extendable Hashing Questions in pass papersB+ Tree PropertiesB+ Tree Properties– Balanced Tree Same height for paths from root to leaf Given a search-key K, nearly same access timefor different K values– B+ Tree is constructed by parameter n Each Node (except root) has n/2 to n pointers Each Node (except root) has n/2-1 to n-1search-key valuesGeneral case for nCase for n=3K K K K K1 2 1 2 n-1P P1 P P 1 P P P2 3 2 n-1 nB+ Tree PropertiesTutorial 8.1 Search keys are sorted in order– K < K < … =K2 3i i i-1Key values in S < K1 1S S S1 2 3K <= Key values in S < K1 2 2Leaf NodeP3K K …1 2P–P points record or bucket with1Pi2search key value KRecord of K Record of Ki1 2–P points to the neighbor leafRecord of Kn 2node…B+ Tree SearchingTutorial 8.2 Given a search-value k– Start from the root, look for the largest search-key value (K ) in the node <= kl– Follow pointer P to next level, until reach al+1K <=k