Microsoft PowerPoint - 080802.ppt1 Similar to B trees, with a few slight differences All data is stored at the leaf nodes (leaf pages); all other nodes (index pages) only store keys Leaf pages are linked to each other Keys may be duplicated; every key to the right of a particular key is >= to that key 9, 16 2, 7 12 18 1 7 9 3, 4, 6 12 16 19 Insert at bottom level If leaf page overflows, split page and copy middle element to next
Section 103 Webpage
