DOC PREVIEW
UMD CMSC 420 - B-Trees

This preview shows page 1-2-3-21-22-23-42-43-44 out of 44 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

B-TreesCMSC 420: Lecture 9Another way to achieve “balance”•Height of a perfect binary tree of n nodes is O(log n).•Idea: Force the tree to be perfect.-Problem: can’t have an arbitrary # of nodes. -Perfect binary trees only have 2h-1 nodes•So: relax the condition that the search tree be binary.•As we’ll see, this lets you have any number of nodes while keeping the leaves all at the same depth.Global balance instead of the local balance of AVL trees.2,3 Trees•All leaves are at the same level.•Each internal node has either 2 or 3 children.•If it has:-2 children => it has 1 key-3 children => it has 2 keys67 75keys < 67keys 68...74keys > 7524keys < 24keys > 242-node:3-node:2,3 Tree Find (multiway searching)5011 45 49 55 60627312 1917 4225Find 19Standard BST-type walk down the tree. At each node have to examine each key stored there.2,3 Tree Find (multiway searching)5011 45 49 55 60627312 1917 4225Find 19Standard BST-type walk down the tree. At each node have to examine each key stored there.2,3 Tree Find (multiway searching)5011 45 49 55 60627312 1917 4225Find 19Standard BST-type walk down the tree. At each node have to examine each key stored there.2,3 Tree Find (multiway searching)5011 45 49 55 60627312 1917 4225Find 19Find 62Standard BST-type walk down the tree. At each node have to examine each key stored there.2,3 Tree Find (multiway searching)5011 45 49 55 60627312 1917 4225Find 19Find 62Standard BST-type walk down the tree. At each node have to examine each key stored there.2,3 Tree Insertion7311 69 70 76 80949817 2522 682,3 Tree Insertion7311 69 70 76 10280949817 2522 682,3 Tree Insertion7311 69 70 76 10280949817 2522 682,3 Tree Insertion7311 69 70 76 10280949817 2522 682,3 Tree Insertion7311 69 70 76 1310280949817 2522 682,3 Tree Insertion7311 69 70 76 1310280949817 2522 682,3 Tree Insertion7311 69 70 76 13 102Overflow!80949817 2522 682,3 Tree Insertion7311 69 70 76 13 102Overflow!Try Key Rotation: Look for left or right sibling with some space, move a parent key into it, and a child key into the parent80949817 2522 682,3 Tree Insertion7311 69 70 76 13 102Overflow!Try Key Rotation: Look for left or right sibling with some space, move a parent key into it, and a child key into the parent80949817 2522 682,3 Tree Insertion7311 69 70 76 13 102Overflow!Try Key Rotation: Look for left or right sibling with some space, move a parent key into it, and a child key into the parent80949817 2522682,3 Tree Insertion7311 69 70 76 13 102Overflow!Try Key Rotation: Look for left or right sibling with some space, move a parent key into it, and a child key into the parent809498172522682,3 Tree Insertion –!When key rotation fails11 69 70 76 13 10280949822 2517 6827732,3 Tree Insertion –!When key rotation fails11 69 70 76 13 10280949822 2517 6827732,3 Tree Insertion –!When key rotation fails11 69 70 76 13 10280949822 2517 6827732,3 Tree Insertion –!When key rotation fails11 69 70 76 13 10280949822 2517 6827Overflow!If both siblings are filled, you have to split the node.732,3 Tree Insertion –!When key rotation fails11 69 70 76 13 10280949817 682722 2725Overflow!If both siblings are filled, you have to split the node.732,3 Tree Insertion –!When key rotation fails11 69 70 76 13 10280949822 2717 6825Overflow!73May have to recursively split nodes, working back to the root.2,3 Tree Insertion –!When key rotation fails11 69 70 76 13 10280949822 2717 6825Overflow!73May have to recursively split nodes, working back to the root.2,3 Tree Insertion –!When key rotation fails11 69 70 76 13 10280949822 2725Overflow!17 6873May have to recursively split nodes, working back to the root.2,3 Tree Insertion –!Another Splitting Example11 69 70 76 80949822 2717 68732510213852,3 Tree Insertion –!Another Splitting Example11 69 70 76 80949822 2717 68732510213852,3 Tree Insertion –!Another Splitting Example11 69 70 76 80949822 2717 68732510213852,3 Tree Insertion –!Another Splitting Example11 69 70949822 2717 687325102138576 85802,3 Tree Insertion –!Splitting at the root11 69 7022 2717 68732598 1021376948085872,3 Tree Insertion –!Splitting at the root11 69 7022 2717 68732598 1021376948085872,3 Tree Insertion –!Splitting at the root11 69 7022 2717 68732598 1021376948085871052,3 Tree Insertion –!Splitting at the root11 69 7022 2717 68732598 1021376948085871052,3 Tree Insertion –!Splitting at the root11 69 7022 2717 68732513769480858710598 1051022,3 Tree Insertion –!Splitting at the root11 69 7022 2717 6873251376858710598 10580 102942,3 Tree Insertion –!Splitting at the root11 69 7022 2717 687325137685 8798 10580 102942,3 Tree Insertion –!Splitting at the root11 69 7022 2717 68137685 8798 10580 1027325 94(b+1)/2 -1 keys(b+1)/2 -1 keysFrom 2,3-Trees to a,b-trees•An a,b-tree is a generalization of a 2,3-tree, where each node (except the root) has between a and b children.•Root can have between 2 and b children.•We require that:-a ≥"2 (can’t allow internal nodes to have 1 child)-b ≥"2a - 1 (need enough children to make split work)b keys1 keyOverflow!(b+1)/2 children ≥ a = ab+1 children(b+1)/2 children ≥ a = aa,b Insertions & DeletionsA B C D ED EA BCC DBAA B C D splitmergeC D EBAD EA BCkey rotationDeletion Details•Try to borrow a key from a sibling if you have one that has an extra (≥"1 more than the minimum)•Otherwise, you have a sibling with exactly the minimum number a-1 of keys.•Since you are underflowing, you must have one less than the minimum number of keys = a-2.•Therefore, merging with your sibling produces a node with a-1 + a-2 = 2a-3 keys. •This is one less than the maximum (2a-2 keys), so we have room to bring down the key that split us from our sibling.B-trees•A B-tree of order b is an a,b-tree with b = 2a-1-In other words, we choose the largest allowed a. •Want to have large b if bringing a node into memory is slow (say reading a disc block), but scanning the node once in memory is fast.•b is usually chosen to match characteristics of the device.•Ex. B-tree of order 1023 has a = 512.-If this B-tree stores n = 10 million records, its height no more than O(loga n) ≈ 2.58. So only around 3 blocks need to be read from disk.Each node (page) is at least 50% full.What if b is very large?•Need to be able to find which subtree to traverse.•Could linearly search through keys –"technically constant time if b is a constant, but may be time


View Full Document

UMD CMSC 420 - B-Trees

Download B-Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view B-Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view B-Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?