Ch10 BTree

Information about Ch10 BTree

Published on November 29, 2007

Author: BeatRoot

Source: authorstream.com

Content

B+-Tree Index:  B+-Tree Index Chapter 10 Modified by Donghui Zhang Nov 9, 2005 Motivation:  Motivation Suppose every disk page holds 133 records. You are given 1334 = 0.3 billion records. They occupy 1333 = 2.3 million disk pages. You can utilize a small memory buffer of 134 pages. You can build an index structure. Given the key of a record, what is the minimum guaranteed number of disk I/Os to find the record? Content:  Content B+-tree index Structure Search Insert Delete Bulk-loading a B+-tree Aggregation Query SB-tree B+ Tree Structure:  B+ Tree Structure Insert/delete at log F N cost; keep tree height-balanced. (F = fanout, N = # leaf pages) Minimum 50% occupancy (except for root). Each node contains d <= m <= 2d entries. The parameter d is called the order of the tree. Supports equality and range-searches efficiently. B+ Tree Equality Search:  B+ Tree Equality Search Search begins at root, and key comparisons direct it to a leaf. Search for 15*… Based on the search for 15*, we know it is not in the tree! Root 17 24 30 2* 3* 5* 7* 14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39* 13 B+ Tree Range Search:  B+ Tree Range Search Search all records whose ages are in [15,28]. Equality search 15*. Follow sibling pointers. Root 17 24 30 2* 3* 5* 7* 14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39* 13 B+ Trees in Practice:  B+ Trees in Practice Typical order: 100. Typical fill-factor: 67%. average fanout = 133 Can often hold top levels in buffer pool: Level 1 = 1 page = 8 KB Level 2 = 133 pages = 1 MB Level 3 = 17,689 pages = 145 MB Level 4 = 2,352,637 pages = 19 GB With 1 MB buffer, can locate one record in 19 GB (or 0.3 billion records) in two I/Os! Inserting a Data Entry into a B+ Tree:  Inserting a Data Entry into a B+ Tree Find correct leaf L. Put data entry onto L. If L has enough space, done! Else, must split L (into L and a new node L2) Redistribute entries evenly, copy up middle key. Insert index entry pointing to L2 into parent of L. This can happen recursively To split index node, redistribute entries evenly, but push up middle key. (Contrast with leaf splits.) Splits “grow” tree; root split increases height. Tree growth: gets wider or one level taller at top. Inserting 8* into Example B+ Tree:  Inserting 8* into Example B+ Tree Find leaf, in the same way as the Search algorithm. Handle overflow by splitting. Root 17 24 30 2* 3* 5* 7* 14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39* 13 Inserting 8* into Example B+ Tree:  Inserting 8* into Example B+ Tree Observe how minimum occupancy is guaranteed in both leaf and index pg splits. Note difference between copy-up and push-up; be sure you understand the reasons for this. 2* 3* 5* 7* 8* 5 Entry to be inserted in parent node. (Note that 5 is continues to appear in the leaf.) s copied up and appears once in the index. Contrast Example B+ Tree After Inserting 8*:  Example B+ Tree After Inserting 8* Notice that root was split, leading to increase in height. In this example, we can avoid split by re-distributing entries; however, this is usually not done in practice. 2* 3* Root 17 24 30 14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39* 13 5 7* 5* 8* Deleting a Data Entry from a B+ Tree:  Deleting a Data Entry from a B+ Tree Start at root, find leaf L where entry belongs. Remove the entry. If L is at least half-full, done! If L has only d-1 entries, Try to re-distribute, borrowing from sibling (adjacent node with same parent as L). If re-distribution fails, merge L and sibling. If merge occurred, must delete entry (pointing to L or sibling) from parent of L. Merge could propagate to root, decreasing height. Deleting 19* and 20*:  Deleting 19* and 20* 2* 3* Root 17 24 30 14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39* 13 5 7* 5* 8* Deleting 19* is easy. Deleting 20* is done with re-distribution. After Deleting 19* and 20* :  After Deleting 19* and 20* Notice, in re-distribution, how middle key is copied up. If delete 24*… 2* 3* Root 17 30 14* 16* 33* 34* 38* 39* 13 5 7* 5* 8* 22* 24* 27 27* 29* ... And Then Deleting 24*:  ... And Then Deleting 24* Must merge. Observe `toss’ of index entry (on right), and `pull down’ of index entry (below). 30 22* 27* 29* 33* 34* 38* 39* 2* 3* 7* 14* 16* 22* 27* 29* 33* 34* 38* 39* 5* 8* Root 30 13 5 17 Example of Non-leaf Re-distribution:  Example of Non-leaf Re-distribution Tree is shown below during deletion of 24*. (What could be a possible initial tree?) In contrast to previous example, can re-distribute entry from left child of root to right child. Root 13 5 17 20 22 30 After Re-distribution:  After Re-distribution Intuitively, entries are re-distributed by `pushing through’ the splitting entry in the parent node. It suffices to re-distribute index entry with key 20; we’ve re-distributed 17 as well for illustration. 14* 16* 33* 34* 38* 39* 22* 27* 29* 17* 18* 20* 21* 7* 5* 8* 2* 3* Root 13 5 17 30 20 22 Bulk Loading of a B+ Tree:  Bulk Loading of a B+ Tree If we have a large collection of records, and we want to create a B+ tree on some field, doing so by repeatedly inserting records is very slow. Bulk Loading can be done much more efficiently. Initialization: Sort all data entries, insert pointer to first (leaf) page in a new (root) page. Sorted pages of data entries; not yet in B+ tree Root Bulk Loading (Contd.):  Bulk Loading (Contd.) Index entries for leaf pages always entered into right-most index page just above leaf level. Assume pages in the rightmost path to have double page size. Split when double plus one. 3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44* Root Data entry pages not yet in B+ tree 6 3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44* 6 Root 12 20 not yet in B+ tree Data entry pages 10 12 20 10 23 Summary of Bulk Loading:  Summary of Bulk Loading Option 1: multiple inserts. Slow. Does not give sequential storage of leaves. Option 2: Bulk Loading Has advantages for concurrency control. Fewer I/Os during build. Leaves will be stored sequentially (and linked, of course). Can control “fill factor” on pages. Buffering:  Buffering Try search 22, insert 8. I1 17 24 30 2* 3* 5* 7* 14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39* 13 L1 L2 L3 L4 L5

Related presentations


Other presentations created by BeatRoot

Mod6
27. 08. 2007
0 views

Mod6

GCSE Russia 1914 41
12. 10. 2007
0 views

GCSE Russia 1914 41

rioforum110906
22. 10. 2007
0 views

rioforum110906

UNIVERSITE AU COEUR PORTUAIRE
23. 10. 2007
0 views

UNIVERSITE AU COEUR PORTUAIRE

SevereWeatherPrez
07. 10. 2007
0 views

SevereWeatherPrez

Galaxies Big Bang
27. 08. 2007
0 views

Galaxies Big Bang

Easy REading Slide Show
27. 08. 2007
0 views

Easy REading Slide Show

cathy
27. 08. 2007
0 views

cathy

Jennex
01. 10. 2007
0 views

Jennex

Akzo Nobel
12. 10. 2007
0 views

Akzo Nobel

Airlift Ops2
22. 08. 2007
0 views

Airlift Ops2

CH05
04. 10. 2007
0 views

CH05

RABIES PGI
15. 11. 2007
0 views

RABIES PGI

Leucograma interpret RN
28. 12. 2007
0 views

Leucograma interpret RN

information retrieval lecture
29. 12. 2007
0 views

information retrieval lecture

Substitution Codes changes
01. 01. 2008
0 views

Substitution Codes changes

wetlandsPres
03. 01. 2008
0 views

wetlandsPres

lec3ai2
27. 08. 2007
0 views

lec3ai2

CopyofAncientRome
07. 12. 2007
0 views

CopyofAncientRome

AirliftOps1
22. 08. 2007
0 views

AirliftOps1

SOC 29COM 7B
22. 10. 2007
0 views

SOC 29COM 7B

Ru Keng Su
27. 08. 2007
0 views

Ru Keng Su

MMA2 end
07. 10. 2007
0 views

MMA2 end

vegnut
09. 07. 2007
0 views

vegnut

Vanilla Sky
09. 07. 2007
0 views

Vanilla Sky

The Beatles
09. 07. 2007
0 views

The Beatles

sexlies
09. 07. 2007
0 views

sexlies

Sephora
09. 07. 2007
0 views

Sephora

Placici madona
09. 07. 2007
0 views

Placici madona

Nectaria Gizani
22. 08. 2007
0 views

Nectaria Gizani

EU Enlargement
26. 11. 2007
0 views

EU Enlargement

lhj TudorMonarchs
22. 08. 2007
0 views

lhj TudorMonarchs

Zhigang Zhu
28. 09. 2007
0 views

Zhigang Zhu

20070624 tcf slides
12. 10. 2007
0 views

20070624 tcf slides

NELSON PPT 1e PPTchap11
19. 02. 2008
0 views

NELSON PPT 1e PPTchap11

Freight Trends
26. 02. 2008
0 views

Freight Trends

WhyERE v2
03. 01. 2008
0 views

WhyERE v2

CVFM CVO GCM Indiana
28. 02. 2008
0 views

CVFM CVO GCM Indiana

Presentation63
21. 11. 2007
0 views

Presentation63

arc IMS manager
22. 08. 2007
0 views

arc IMS manager

Whales Dolphins
12. 03. 2008
0 views

Whales Dolphins

Don Giovanni 1787
21. 03. 2008
0 views

Don Giovanni 1787

PresentationRus
27. 03. 2008
0 views

PresentationRus

Global IP Mobility IETF
07. 04. 2008
0 views

Global IP Mobility IETF

07 LectureOutline
28. 03. 2008
0 views

07 LectureOutline

20 Trend Micro
30. 03. 2008
0 views

20 Trend Micro

ch17 CMBA 401
10. 04. 2008
0 views

ch17 CMBA 401

CTradeMar2002
14. 04. 2008
0 views

CTradeMar2002

ESM 297 Week 5
29. 02. 2008
0 views

ESM 297 Week 5

lect 17
17. 04. 2008
0 views

lect 17

sartre1
27. 08. 2007
0 views

sartre1

Channels measured by BARB
27. 08. 2007
0 views

Channels measured by BARB

Frederick Community College
02. 11. 2007
0 views

Frederick Community College

PUSSYCAT DOLLS
09. 07. 2007
0 views

PUSSYCAT DOLLS

ZadehBISC2004
02. 10. 2007
0 views

ZadehBISC2004

2004 miller
22. 08. 2007
0 views

2004 miller

Whitney eVLBI
09. 10. 2007
0 views

Whitney eVLBI

ch17 sec3
26. 03. 2008
0 views

ch17 sec3

Harris
09. 08. 2007
0 views

Harris

PelikanIBM
03. 10. 2007
0 views

PelikanIBM

retriever preso
09. 07. 2007
0 views

retriever preso

What is rock music2
27. 08. 2007
0 views

What is rock music2