B-Trees PDF

Preview

Summary

B-Trees...

Description

B-Trees © Dave Bockus Acknowledgements to: Dr Frederic Maire Brisbane, Queensland, AUSTRALIA for some of the material found in this presentation

Motivation • When data is too large to fit in main memory, then the number of disk accesses becomes important. • A disk access is unbelievably expensive compared to a typical computer instruction (mechanical limitations). • One disk access is worth about 200,000 instructions. • The number of disk accesses will dominate the running time. 2

Motivation Cont.. • Secondary memory (disk) is divided into equalsized blocks (typical sizes are 512, 2048, 4096 or 8192 bytes) • The basic I/O operation transfers the contents of one disk block to/from main memory. • Our goal is to devise a multiway search tree that will minimize file accesses (by exploiting disk block read). 3

m-ary Trees K1 K2 K3 K4

Etc. T1

T2

K < K1

K1 < K < K2

T3

• A node contains multiple keys. • Order of subtrees is based on parent node keys • If each node has m children & there are n keys then the average time taken to search the tree is logmn.

4

Searching m-ary Trees  A generalized SOT will visit all keys in ascending order. for (i==1;i...