What’s the difference between B-tree and B+tree?

hbghlyj

youtube.com/watch?v=K1a2Bk8NrYQ

Feature	B-tree	B+tree
Data Storage	Data (keys and values) stored in both internal and leaf nodes	Data stored only in leaf nodes; internal nodes store only keys
Leaf Node Linking	Leaf nodes are not linked together	Leaf nodes are linked in a linked list for fast range queries
Search Efficiency	May stop at internal node if key is found	Always goes down to leaf node even if key is in internal node
Range Queries	Slower, as requires in-order traversal	Faster, due to linked leaves enabling sequential scan
Tree Height	Slightly shorter, since data is stored in all nodes	Slightly taller, as data only at leaves
Space Utilization	Better (internal nodes used for data too)	Less efficient (internal nodes don’t store data)
Insertion/Deletion	More complex, as data movement can affect any level	Simpler logic, since data moves only in leaf level

hbghlyj

In a B+tree, the leaf nodes (which store all the actual data entries) are connected in a linked list, typically left to right. For example:
          [30]       [60]
         /   \       /   \
       ...   ...   ...   ...
        ↓     ↓     ↓     ↓
     [10 20]→[30 40 50]→[60 70 80]→...

When you want to retrieve a range of values, such as all values from 30 to 75, here’s what happens:

• Find the start (30) using the tree structure.
• Once at the leaf containing 30, just follow the linked list of leaves to collect 30, 40, 50, 60, 70.
• Stop when you pass 75.

This avoids having to go back up the tree for each next key — unlike in a B-tree, where values might be scattered across multiple internal nodes, and sequential access means repeated tree traversals.

Linked leaves allow a single left-to-right traversal once you hit the start of your range.

This enables efficient O(n) scanning over a range (where n is the number of items in the range), instead of O(n log m) if you had to re-traverse the tree n times (where m is the order of the tree).