11

I'm pretty familiar with a B Tree, mainly having to keep the databases well fed with electricity, air conditioning, and harddrive space. I associate with a double (doubl[ie,ey]?) linked list.

Today, one of the developers at lunch mentioned a R tree.

I hopped on Wikipedia and started reading. It sounded an awful like a taller B tree. Unfortunately, not having a deep math background makes it tough to understand what some of my coworkers are talking about.

I was hoping if someone could clarify a few differences between a B tree and a R tree. I'll probably end up asking the guys anyways, but there is no guarantee that they will answer my question. More than likely they will start rambling about God knows what. . .

Improve this question
7
  • a BTree is definitely not like a double linked list. A tree allows access in log(n) operations instead of proportional to n, as on lists.
    – Javier
    Jul 28, 2011 at 3:39
  • @Javier: the leaf nodes of a b-tree index are usually a doubly linked list to allow for quick sibling retrieval of index nodes.
    – Jordan
    Jul 28, 2011 at 4:08
  • 1
    Being a purely technical question, this belongs to StackOverflow (please don't repost it there though, it will be automigrated if enough people vote to close it here).
    – Péter Török
    Jul 28, 2011 at 7:54
  • 1
    This is on-topic here: Programmers.SE is for concept questions about programming. Stack Overflow is for when you actually have code you need help with.
    – user8
    Jul 28, 2011 at 9:44
  • 2
    @Peter Torok: Under the old system, this WOULD of been a SO question. But now that this site exists.
    – surfasb
    Jul 28, 2011 at 15:59

2 Answers 2

Reset to default
8

An R Tree can be thought of as generalization of a b-tree. Where a b-tree provides O(log n) access over a "bounded range" of the keys it contains, an R Tree provides O(log n) access over a "K dimensional region" of the keys it contains.

If you wanted to map zip codes to county names, You could use a B-Tree, since you could ask it "What are all of the counties with zipcodes between 60000 and 61000?" However, a B-Tree would be ill suited to map GPS coordinates to county names for queries like "What are all of the counties within 100 miles of Chicago?", since it only orders its keys on a single dimension. An R-Tree breaks its keys up according to overlapping bounding boxes, and so it's a natural way to store keys when you need to query on multiple dimensions.

Improve this answer
2
  • I like the analogy.
    – surfasb
    Jul 28, 2011 at 5:22
  • 1
    More of a concrete example than an analogy, It's exactly how these index algorithms are used.
    – SingleNegationElimination
    Jul 28, 2011 at 5:31
7

Most tree structures can be reduced to some form of linked list, as long as you ignore how the list is constructed (specifically, how elements are added and removed, and how the nodes are rebalanced, if applicable). It's essentially the insertion/deletion/retrieval algorithm that distinguishes one data structure from another.

Nodes in an R-Tree generally contain a bounding box, which allows you to efficiently index locations, as you might need if you wanted to search for records "near" a particular location. Elements in a B-Tree have a simpler ordering; you can directly compare whether something is greater than or equal to another element. In an R-Tree, the purpose of each entry is to determine what elements are contained in a bounding box.

A B-Tree allows you to efficiently search orderable items in secondary memory (like a hard disk), and an R-Tree allows you to efficiently search for elements which are "at" or "near" a particular point or bounding box, also in secondary memory.

Improve this answer
3
  • It sounds like the R tree starts to show its distinction as the number of elements grows, correct? Or is that a little too simplified?
    – surfasb
    Jul 28, 2011 at 4:24
  • I think that given a similar number of nodes, you wouldn't see a particular difference in space usage except for the linear cost of the bounding box data at non-leaf nodes. But you simply can't represent bounding boxes efficiently in the conventional definition of a B-Tree, so, you'd certainly use a lot more space if you tried to represent spatial information in a B-Tree. The R-Tree is for spatial relationships, the B-Tree supports only single-dimension ordering.
    – JasonTrue
    Jul 28, 2011 at 4:32
  • 2
    @JasonTrue: Actually, there are efficient ways to linearize bounding boxes for B-Tree indexing: en.wikipedia.org/wiki/Geohash . Although hashes are "efficient", they aren't particularly convenient. An arbitrary bounding box query is likely to take 9 separate queries for a 2 dimensional space, and if the box overlaps a major axis (say, The International Dateline), the number of queries may double or quadruple and it becomes very cumbersome to use. In spite of this, it's still an option when linear indexes are the only kind available.
    – SingleNegationElimination
    Jul 28, 2011 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.