Tutorial 1.0

Description

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

Informations

• Publié par: Sawyong
• Nombre de lectures: 12
• Langue: English

Extrait

B+

Tree

and

Hashin

•

•

•

•

•

•

•

B+

B+

B+

B+

Tree

Tree

Tree

Tree

Properties

Searching

Insertion

Deletion

Static Hashing

Extendable Hashing

Questions in pass papers

B+ Tree Properties B+ Tree Properties

– Balanced Tree • Same height for paths from root to leaf • Given a search-key K, nearly same access time for different K values – B+ Tree is constructed by parametern • Each Node (except root) hasn/2to n pointers • Each Node (except root) hasn/2-1 to n-1 search-key values Case for n=3  General case for n K 1 K 2 K 1 K 2 P 1 P 2 P 3 P 1 P 2

K n-1

P n-1 P n

B+ Tree Properties Tutorial 8.1

• Search keys are sorted in order – K 1 < K 2 < … <K n-1 •Non-leaf Node Each ke -search values in subtree S i K 1 K 2 p – ointedb y yP i < K i , >=K i-1 P 1 P 2 P 3 K 1 vylaeK lavyiseuSn siuenS Ke<= 1 2 < < K K 1 2 S 1 S 2 S 3 •Leaf Node –P i points record or bucket with P 1 K 1 P 2 K P 3 … search key value K i Record of K 1 Record of K 2 –P n points to the neighbor leaf Record of K 2 node …

B+ Tree Searching Tutorial 8.2

•

Given a search-value k – Start from the root, look for thelargestsearch- key value (K l ) in the node <= k – Follow pointer P l+1 to next level, until reach a leaf node K l <=k<K l+1 K 1 K 2 … K l K l+1 n-1 P 1 P 2 P 3 P l+1 P P n – If k is found to be equal to K l in the leaf, follow P l to search the record or bucket  K l K l+1 l P l k = K l Record of K l …

RecodrofK

B+ Tree Insertion Tutorial 8.3

• Overflow – When number of search-key values exceed n-1 7 9 13 15 Insert 8

–Leaf Node •Split into two nodes: –1 st node contains(n-1)/2values –2 nd node contains remaining values –Copy the smallest search-key value of the 2 nd node to parent node

9

7 8

9 13 15

B+ Tree Insertion Tutorial 8.3

• Overflow – When number of search-key values exceed n-1 7 9 13 15 Insert 8 –Non-Leaf Node •Split into two nodes: –1 st node containsn/2-1 values –Move the smallest of the remaining values, together with pointer, to the parent –2 nd node contains the remaining values 9

7 8

13 15

B+ Tree Insertion Tutorial 8.3

•

Example 1: Construct a B + tree for (1, 4, 7, 10, 17, 21, 31, 25, 19, 20, 28, 42) with n=4 .

1

1

4 7

4

7

17

1

7 10

4

7

7 10

17 21

1

B+ Tree Insertion

1

4

• 1, 4, 7, 10, 17, 21, 31, 25, 19, 20, 28, 42

4

7 17 25

7

7 10

7

10

17

17

19

17 21

20 25

20 21

25

31

25

31

1

B+ Tree Insertion Tutorial 8.3

• 1, 4, 7, 10, 17, 21, 31, 25, 19, 20, 28, 42

4

7

10

7

17

17

19

20

21

20

25

31

25 28

31

42

B+ Tree Insertion Tutorial 8.3

• Example 2: n=3, insert 4 into the following B+Tree 9 10

2

4

7

4 5

9

A

2 5

B

0

C

7

8

Leaf A

D

Subtree C

Leaf B

Subtree D