Ch10 BTree

50 %
50 %
Information about Ch10 BTree
Entertainment

Published on November 29, 2007

Author: BeatRoot

Source: authorstream.com

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

Add a comment

Related presentations

Related pages

Rockefeller Center Christmas Tree Lighting | Rockefeller ...

The Rockefeller Center Christmas Tree is a world-wide symbol of the holidays and a sight to behold.
Read more

Chapter 10. Tuning

... reside under the indexedAttributes property of the org.apache.directory.server.core.partition.impl.btree ... value>10 Read more

[Chapter 10] 10.3 Record-Oriented Approach

The $DB_BTREE constant tells the library to use the btree format, allowing the key-value pairs to be stored in a sorted, balanced multiway tree; ...
Read more

Indexes implemented using: – Hash indexes – B-tree ...

Indexes implemented using: – Hash indexes – B-tree indexes – Bitmap indexes • DBMSs from CSIS 304 at Concordia Moorhead
Read more

Introduction to Algorithms 2nd Edition - Chegg - Get 24/7 ...

Answer to Write pseudocode for B-TREE-DELETE.. ... Over 90% of students who use Chegg Study report better grades.
Read more

Starting Out With Java: From Control Structures Through ...

Starting Out with Java: From Control Structures through Data Structures 2nd Edition. 1606 step-by-step solutions; Solved by publishers, ... (Node bTree ...
Read more

assignment4_solution b+tree - Database Systems Instructors ...

View Homework Help - assignment4_solution b+tree from CIS 662 at جامعة اليرموك. Database Systems Instructors: Hao-Hua Chu Winston Hsu Fall
Read more

[Chapter 10] 10.4 The sendmail.cf File - DIABLOTIN : le ...

The most commonly supported database types for sendmail V8 are dbm, btree, and hash. [10] All of these types can be made with the makemap command.
Read more

[Chapter 10] 10.6 Rewriting the Mail Address

10.6 Rewriting the Mail Address . ... Common types are dbm, hash, btree, and nis. There are many more, all of which are described in Appendix E.
Read more

Donghui Zhang's Home Page

Donghui Zhang Director of Software Development Paradigm4, Inc 186 Third Av Waltham, MA 02451 Email: dzhang AT paradigm4 DOT com: Donghui Zhang received a ...
Read more