CODEWITHSUNDEEP
algorithmtreeindexingb-tree
Niklas Rosencrantz
Niklas Rosencrantz

Reputation: 26647

How to calculate that a B+ tree is O(log(n)) for lookups

I'm studying B+trees for indexing and I try to understand more than just memorizing the structure. As far as I understand the inner nodes of a B+tree forms an index on the leaves and the leaves contains pointers to where the data is stored on disk. Correct? Then how are lookups made? If a B+tree is so much better than a binary tree, why don't we use B+trees instead of binary trees everywhere?

I read the wikipedia article on B+ trees and I understand the structure but not how an actual lookup is performed. Could you guide me perhaps with some link to reading material?

What are some other uses of B+ trees besides database indexing?

Upvotes: 4

Views: 2834

Answers (2)

Matthieu M.
Matthieu M.

Reputation: 299890

I'm studying B+trees for indexing and I try to understand more than just memorizing the structure. As far as I understand the inner nodes of a B+tree forms an index on the leaves and the leaves contains pointers to where the data is stored on disk. Correct?

No, the index is formed by the inner nodes (non-leaves). Depending on the implementation the leaves may contain either key/value pairs or key/pointer to value pairs. For example, a database index uses the latter, unless it is an IOT (Index Organized Table) in which case the values are inlined in the leaves. This depends mainly on whether the value is insanely large wrt the key.

Then how are lookups made?

In the general case where the root node is not a leaf (it does happen, at first), the root node contains a sorted array of N keys and N+1 pointers. You binary search for the two keys S0 and S1 such that S0 <= K < S1 (where K is what you are looking for) and this gives you the pointer to the next node.

You repeat the process until you (finally) hit a leaf node, which contains a sorted list of key-values pairs and make a last binary search pass on those.

If a B+tree is so much better than a binary tree, why don't we use B+trees instead of binary trees everywhere?

  • Binary trees are simpler to implement. One though cookie with B+Trees is to size the number of keys/pointers in inner nodes and the number of key/values pairs in leaves nodes. Another though cookie is to decide on the low and high watermark that leads to grouping two nodes or exploding one.
  • Binary trees also offer memory stability: an element inserted is not moved, at all, in memory. On the other hand, inserting an element in a B+Tree or removing one is likely to lead to elements shuffling
  • B+Trees are tailored for small keys/large values cases. They also require that keys can be duplicated (hopefully cheaply).

Could you guide me perhaps with some link to reading material?

I hope the rough algorithm I explained helped out, otherwise feel free to ask in the comments.

What are some other uses of B+ trees besides database indexing?

In the same vein: file-system indexing also benefits.

The idea is always the same: a B+Tree is really great with small keys/large values and caching. The idea is to have all the keys (inner nodes) in your fast memory (CPU Cache >> RAM >> Disk), and the B+Tree achieves that for large collections by pushing keys to the bottom. With all inner nodes in the fast memory, you only have one slow memory access at each search (to fetch the value).

Upvotes: 4

memo
memo

Reputation: 441

B+ trees are better than binary tree all the dbms use them,

a lookup in B+Tree is LOGF N being F the base of LOG and the fan out. The lookup is performed exactly like in a binary tree but with a bigger fan out and lower height thats why it is way better.

B+Tree are usually known for having the data in the leaf(if they are unclustered probably not), this means you dont have to make another jump to the disk to get the data, you just take it from the leaf.

B+Tree is used almost everywhere, Operating Systems use them, datawarehouse (not so much here but still), lots of applications.

B+Tree are perfect for range queries, and are used whenever you have unique values, like a primary key, or any field with low cardinality.

If you can get this book http://www.amazon.com/Database-Management-Systems-Raghu-Ramakrishnan/dp/0072465638 its one of the best. Its basically the bible for any database guy.

Upvotes: 3

Related Questions