Navigating Massive Disk Datasets with Multi-Level Index Trees

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 17.9 Free with a free account

Navigating Massive Disk Datasets with Multi-Level Index Trees

Data Structures and Algorithms · Chapter 17: Graphs and MemorySection 17.9 · lesson 86 of 879 min · free with a free account

← Why Frequently Used Data Lives in Faster, Smaller MemoryNext lesson: Arranging Data Too Large to Fit in Main Memory →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

How B-trees and B+ trees find disk records in few reads.

  • Measure the cost of disk algorithms in block reads and writes
  • Estimate a B+ tree's height from block size and branching factor
  • Compare B-trees with B+ trees and trace a leaf split on insert
  • Explain when a database index beats a full table scan and when it loses

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,196 words). Read along, or search it.

Opening Question

Four Reads Among a Million Rows

A table of a million customer rows sits on disk. A query asks for the row with one particular id. Reading the table from the start touched over 15,000 blocks on average, in one test. An index tree found the same row in four block reads. How can four reads be enough, and when does an index stop helping?

Cost Model

Counting Block Reads and Writes

A disk doesn't hand over single bytes. It moves fixed-size blocks, here 4,096 bytes, and one block read or write is one I/O. Asking for one byte of a block costs as much as asking for all of it. So the cost of a disk algorithm is the number of blocks it reads and writes. Comparing keys inside a block that's already in memory is free in this model, because one transfer takes far longer than any step in memory. So a good disk structure packs each block full of useful entries, and reaches any item through as few blocks as possible.

Block Capacity

Entries per Leaf and Children per Block

How much fits in one block? Our keys and record numbers are 8 bytes each, a child pointer is 4, and each block starts with an 8-byte header. On disk, a child pointer isn't a memory address. It's a block number, so following it means reading that block. A leaf holds 4,096 minus 8, over 16: 255 entries. An inner block holds 340 keys, and so 341 children.

Tree Height

Hundreds of Children Keep Trees Short

Finding a key costs one block per level, so the height is what matters. A balanced binary tree over a million keys has about 20 levels: up to 20 reads. A block with hundreds of children narrows the search by hundreds per read. The height is about log base f of N, for branching factor f. Real blocks run about 70 percent full: about 178 entries per leaf, and 238 children per inner block. A million keys need about 5,600 leaves, 24 blocks above them, and one root: height 3. A billion keys need just one more level: 4. In one test with a million random keys, smaller blocks made taller trees: 5 levels at 512 bytes, 2 at 16 kilobytes.

Quick Check

Levels for Fifty Million Keys

Quick check. A B+ tree on the same 4,096-byte blocks holds 50 million keys. Leaves hold about 178 entries, and inner blocks about 238 children. How many levels does a lookup read? Pause, and decide. Four. Fifty million over 178 is about 281,000 leaves. Over 238, that's about 1,180 blocks, then about five, then one root. Three levels top out around 10 million keys. Twenty-six is what a binary tree would need.

B+ Trees

Signposts Above, Chained Leaves Below

What does each block store? In a B-tree, every block, inner or leaf, holds keys with their record numbers, and each key appears once. In a B+ tree, inner blocks hold only signposts. Every key and record number lives in a leaf, and the leaves are chained in key order. Here, the root's signposts 30, 50, and 70 send smaller keys left, and larger ones right. A range query for 28 to 62 descends once, to the leaf where 28 would be. Then it follows the chain across the leaves, until a key passes 62. It never climbs back up. Notice that the first leaf is read even though none of its keys is in range.

B-Tree Versus B+ Tree

Narrower Inner Blocks and Ordered Scans

Is a B+ tree much faster than a B-tree? With 8-byte record numbers, barely. In one test with a million keys, lookups cost 3.00 reads against 2.99. The B+ tree's real gain is narrower inner blocks: 341 children against 205, because signposts carry no records. With bigger records, the gap widens. If each entry carried a 100-byte row, a B-tree inner block would hold only 36 keys, while a B+ tree's would still hold 340. That, plus cheap ordered scans along the leaf chain, is why databases favor B+ trees.

Buffer Pool

Caching the Top of the Tree

Search reads one block per level, then binary-searches inside the leaf, which is free. Three levels, three reads. But every lookup starts at the root. A buffer pool keeps recent blocks in memory, and evicts the least recently used one when it's full. In one test of 10,000 lookups: no cache, 3 reads each. A cache of 3 blocks keeps the root: 1.97. With 256 blocks, it's under one read per lookup. The top of the tree is tiny. The root and a few dozen inner blocks take about 116 kilobytes, for an index over a million keys.

Insertion

Splitting a Full Leaf

An insert is a search, then a change to the leaf. If the leaf has room, that's one block written. If it overflows, it splits as in lesson 15.3. Say a leaf holds three keys, 30, 35, and 40, and 45 arrives. The old block keeps 30 and 35. A new block takes 40 and 45. And a copy of 40 goes up to the parent as a new signpost. Three reads down the path, then three writes: the old leaf, the new one, and the parent. Only a root split makes the tree taller. Splits are rare with big blocks. Building a million-key tree took 5,583 splits at 4,096 bytes: about 0.6 percent of the inserts.

Insertion Order

Ascending Keys Leave Half-Empty Leaves

Insertion order matters too. Because a split cuts a full leaf in half, leaves end up about 70 percent full after random inserts. Ascending keys always land in the last leaf. When it splits, the left half is never touched again. In one test with 200,000 keys, random order gave leaves 73.9 percent full. Ascending order gave 50.2 percent, and 47 percent more blocks for the same data.

Quick Check

Blocks Written by One Insert

Quick check. Same tiny tree, three keys per leaf, and the parent has room. Block 10 now holds 40 and 45. First 46 is inserted, then 47. How many blocks does the insert of 47 write? Pause, and decide. Three. Inserting 46 just fills block 10, one write. But 47 finds it full, so it splits. Block 10 and a new block 11 are written, and the parent is rewritten with a new signpost. One block would be the case with room to spare.

Database Index

When an Index Loses to a Scan

Now a database index. The test table has a million rows of 128 bytes: 32 per block, 31,250 blocks. The index maps an id to its row's position. Finding one row by scanning read 15,086 blocks on average. Binary search over a sorted table took about 14. The index took 3 tree reads plus 1 for the row: 4. But each row an index finds costs its own block read. At 31,250 rows, just 3.1 percent of the table, the index cost more than a scan. At 10 percent, it cost 100,565 blocks: more than three times a full scan. And every index adds a search and a write to each insert.

Key Takeaways

Disk Index Trees in Brief

To sum up. On disk, the cost is blocks read and written. A node is a block, and a child pointer is a block number. Hundreds of children per block keep the tree short: three levels for a million keys, four for a billion. B+ trees keep records in chained leaves and only signposts inside. Search costs one read per level, and a cached top cuts that to about one. And an index wins for small results, but loses once the rows returned approach the number of data blocks.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Navigating Massive Disk Datasets with Multi-Level Index Trees

Why are B-trees used for databases and disk storage?
B-trees suit disk storage because a disk transfers whole blocks, and each node fills one block with hundreds of keys, so every read narrows the search by hundreds. A balanced binary tree over a million keys needs about 20 levels, while a B+ tree with 4,096-byte blocks needs about three, and a billion keys need about four. Fewer levels mean fewer slow block reads per lookup.
What is the difference between a B-tree and a B+ tree?
In a B-tree, every node, inner or leaf, holds keys with their records or record numbers, and each key appears once. In a B+ tree, inner nodes hold only signpost keys, every record lives in a leaf, and the leaves are chained in key order. That gives B+ trees wider inner nodes and cheap range scans along the leaf chain, which is why databases favor them.
How do you calculate the height of a B+ tree?
A B+ tree's height is about log base f of N, where f is the branching factor and N the number of keys. With leaves holding about 178 entries and inner blocks about 238 children, 50 million keys need about 281,000 leaves, then about 1,180 inner blocks, then about five, then one root: four levels. Three levels top out around 10 million keys.
When is a database index slower than a full table scan?
An index becomes slower than a full scan once a query returns many rows, because each row it finds can cost its own block read. In one test on a million-row table stored in 31,250 blocks, fetching 31,250 rows, about 3.1 percent of the table, already cost more than scanning every block. An index wins for small results, such as one row in four reads, but adds work to every insert.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →