Multiway Search Trees: 2-3 Trees, 2-4 Trees, and B-Trees

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

Multiway Search Trees: 2-3 Trees, 2-4 Trees, and B-Trees

Data Structures and Algorithms · Chapter 15: Balanced Search TreesSection 15.3 · lesson 65 of 8710 min · free with a free account

← AVL Trees: Rebalancing After Every Insertion and DeletionNext lesson: Balanced Trees Compared: Red-Black Trees and TreeMap →

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 2-3 trees, 2-4 trees and B-trees stay balanced with wide nodes.

  • State the node-size and leaf-depth rules of a B-tree of order m
  • Trace insertion with node splits in 2-3 and 2-4 trees
  • Repair underflow after deletion by borrowing from or merging with a sibling
  • Explain why all leaves stay at one depth and how order affects height

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,547 words). Read along, or search it.

Opening Question

More Keys per Node, Fewer Levels

A binary search tree holds one key in each node, and has two children. So a million keys need at least twenty levels. Now suppose a node could hold several sorted keys, and have one more child than it has keys. Each step down would rule out far more of the data, and the tree would be far shorter. What rules keep such a tree tidy as keys come and go?

Definition

Sorted Keys Split the Children

In a multiway search tree, a node with k keys keeps them in sorted order, and has k plus one children. The first child holds every key smaller than the first key. The last child holds every key larger than the last key. And each child in between holds the keys that fall between two neighboring keys. The node kinds are named by their children. A 2-node has one key, a 3-node has two keys, and a 4-node has three.

B-Tree Family

Order m and Its Members

Several keys per node isn't enough by itself. Without more rules, the tree could still grow lopsided. A B-tree adds them. The rules use the order of the tree, m: the largest number of children a node may have. Books differ on this word, so check the definition wherever you read. A 2-3 tree is a B-tree of order three: one or two keys per node. A 2-4 tree has order four: one to three keys. In general, a node of order m holds at most m minus one keys.

Four Rules

Sorted, Not Too Full, Not Too Empty

There are four rules. One: inside a node, the keys are sorted, and they split the key range among the children. Two: not too full. A node holds at most m minus one keys. Three: not too empty. Every node except the root holds at least m over two, rounded up, minus one keys. The root needs just one. And four: all leaves sit at exactly the same depth. That last rule is the one that keeps the tree balanced.

Search

Scanning a Node, Then Stepping Down

Searching a node is like searching a short sorted list. Skip every key smaller than the target. If the next key matches, you're done. Otherwise, step down into the child in the gap where the scan stopped. Here's a 2-3 tree holding 10, 20, up to 90. Search for 70. It's larger than 40, so go to the last child. In the node 60, 80, it falls between them, so take the middle child. And there's 70: three nodes visited. Search for 55. Right of 40, then left of 60, into the leaf 50. A leaf has no children, so 55 is absent. A miss always walks down to a leaf. So a search visits at most one node per level.

Insertion

Splitting an Overflowing Node

Insertion always adds the new key to a leaf, never to an inner node. Search finds the leaf, and the key goes into its sorted place. If the leaf now holds too many keys, it overflows, and it's repaired by a split. Take the middle key. The keys left of it stay in the old node. The keys right of it move to a new node. And the middle key moves up into the parent, between the two halves. The parent may overflow in turn, so the same repair can climb. And if the root splits, a new root appears, holding just the middle key. That's the only way the tree grows taller.

Worked Example

Seven Keys in a 2-3 Tree

Watch a 2-3 tree take 10, 20, 30, 40, 50, 60, 70, in order. The leaf 10, 20 can take one more key only briefly. When 30 arrives, it splits, and 20 goes up as a new root. 40 joins the leaf 30. Then 50 splits it, sending 40 up beside 20. 60 joins 50. And 70 causes two splits in a row. The leaf splits and sends 60 up. That makes the root 20, 40, 60, so the root splits too. 40 becomes a new root. The tree gained its third level, at the top. Every leaf is still at the same depth.

Worked Example

The Same Keys in a 2-4 Tree

Now the same seven keys in a 2-4 tree. After three keys, the leaf holds 10, 20, 30, which is legal here. No split yet. 40 makes it overflow, and 30 goes up. Later, 70 splits the leaf 40, 50, 60. At the end there are only two levels, against three for the 2-3 tree. Bigger nodes mean fewer splits, and a shorter tree.

Quick Check

Inserting Thirty-Five

Quick check. This 2-3 tree holds 20 at the root, with leaves 10 and 30, 40. Insert 35. What happens? Pause, and decide. One split. 35 lands in the leaf as 30, 35, 40, which is one key too many for a 2-3 tree. The middle key is 35 itself, so 35 goes up. The root becomes 20, 35, which has room, so the repair stops there. No new root, and the height stays at two.

Deletion

Borrowing and Merging After Underflow

Deletion is the mirror image. A key is only ever removed from a leaf. If the key sits in an inner node, overwrite it with its predecessor: the largest key of the subtree to its left, which is always in a leaf. Then delete that copy from the leaf. Removing a key can leave a node with too few keys. That's an underflow, and there are two repairs. Borrow: if a neighboring sibling has a spare key, it moves up into the parent, and the separating parent key comes down. The shape doesn't change. Merge: if no sibling can spare one, join the short node, a sibling, and the parent key between them. The parent lost a key, so it may underflow in turn. This 2-3 tree holds 2 and 4 at the root, over leaves 1, 3, and 5, 6. Deleting 5 is plain: the leaf keeps 6. Delete 3 instead. Its leaf empties, but its right sibling 5, 6 has a spare. So 4 comes down, and 5 goes up: a borrow. Delete 1 instead. Its only sibling, 3, has no spare. So 1's empty leaf, the parent key 2, and the leaf 3 merge into one node, 2, 3. And if a merge takes the last key out of the root, the merged node becomes the new root. The tree loses a level, again at the top.

Quick Check

Deleting Forty

Quick check. A 2-3 tree has 30 at the root, with leaves 10, 20, and 40. Delete 40. Which repair follows? Pause, and decide. A borrow. 40's leaf empties, and its left sibling, 10, 20, has a spare key. So 20 moves up into the root, and 30 comes down into the empty leaf. The result is 20 over 10 and 30. A merge happens only when no sibling can spare a key.

Key Insight

Depth Changes Only at the Root

Why do all leaves stay at the same depth, when no step ever checks it? Because no operation ever moves a single leaf up or down. Adding to a leaf, splitting below the root, borrowing, and merging below the root all leave every root-to-leaf path the same length. Only two events change depth: a root split makes every leaf one level deeper, and a merge that empties the root makes every leaf one level shallower. So depth changes only at the root, and always for every leaf at once.

Height

Larger Order, Fewer Levels

So the height is order log n, and the order sets the base of the logarithm. A larger order means fewer levels. In one test with a million random keys, a 2-3 tree was sixteen levels tall, and a search visited about fifteen nodes. Order sixteen gave six levels. Order 128 gave three levels, and about three nodes per search. A binary tree needs at least twenty.

Measured Results

When Nodes Get Too Big

So should a node be as big as possible? Not in memory. A search scans each node from left to right, and a huge node costs hundreds of comparisons. On one test machine, lookup time fell from about 970 nanoseconds, at order three, to about 210, at order sixty-four. That's more than three times faster than Java's TreeSet. But by order 512, it rose again to 375, even with only three levels. The scanning inside each node cost more than the levels it saved.

Arrival Order

Increasing Keys Leave Half-Empty Nodes

Arrival order matters in a different way here. With keys in increasing order, a split's left half is never touched again, because every later key is larger. So 1,000 increasing keys left a 2-3 tree with 994 nodes: about one key each, as empty as the rules allow. A 2-4 tree held about two keys per node. The tree is still balanced, and still short. It just wastes room.

Key Takeaways

Splits, Borrows and Merges

To sum up. A node with k keys has k plus one children. A 2-3 tree is a B-tree of order three, and a 2-4 tree is one of order four. Search scans a node, then steps into a gap: one node per level. Insertion adds to a leaf, and an overflowing node splits and sends its middle key up. Deletion borrows from a sibling, or merges. All leaves stay at one depth, because only the root changes it. And a larger order means fewer levels, though in memory, a huge node costs more to scan.

Think About It

Node Size on a Disk

Here's something to think about. In memory, order sixty-four was the sweet spot. Now suppose every node lives on a disk, and reading one node costs as much as millions of comparisons. Would the best node size grow, or shrink?

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 Multiway Search Trees: 2-3 Trees, 2-4 Trees, and B-Trees

What is a B-tree of order m?
A B-tree of order m is a search tree whose nodes hold sorted keys and have up to m children, with one fewer key than children. Every internal node except the root must have at least ceil(m / 2) children, and all leaves sit at the same depth. A 2-3 tree is a B-tree of order 3 and a 2-4 tree is one of order 4. Textbooks define order slightly differently, so check which definition a source uses.
How does insertion work in a 2-3 tree?
A new key goes into the correct leaf. If that leaf now holds three keys, it splits: the middle key moves up into the parent, and the two outer keys become separate nodes. The parent may overflow in turn and split the same way. When the root splits, its middle key becomes a new root, and the tree grows by one level at the top, keeping every leaf at the same depth.
What is the difference between borrowing and merging in B-tree deletion?
Both repair a node left with too few keys after a deletion. Borrowing applies when an adjacent sibling has a spare key: the parent's separating key moves down into the short node and the sibling's nearest key moves up to replace it. Merging applies when the sibling has no spare: the short node, the sibling and the separating key combine into one node, which removes a key from the parent and can cascade upward.
Why are all leaves in a B-tree at the same depth?
The tree changes height only at the root, which affects every path equally. A split pushes a key up rather than hanging a new node below a leaf, so the tree grows only when the root itself splits and a new root appears above all paths. Likewise, merges can empty the root, and removing it shortens every path by one level. Leaves therefore stay level through any mix of insertions and deletions.

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 →