Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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. . .

share|improve this question
    
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 '11 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 '11 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 '11 at 7:54
    
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 '11 at 9:44
    
@Peter Torok: Under the old system, this WOULD of been a SO question. But now that this site exists. –  surfasb Jul 28 '11 at 15:59

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
I like the analogy. –  surfasb Jul 28 '11 at 5:22
    
More of a concrete example than an analogy, It's exactly how these index algorithms are used. –  TokenMacGuy Jul 28 '11 at 5:31

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.

share|improve this answer
    
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 '11 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 '11 at 4:32
1  
@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. –  TokenMacGuy Jul 28 '11 at 5:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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