You are either not logged in or not registered with our community. Click here to register.
 
December 10, 2016, 12:42:09 PM

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

Click here if you are having problems.
Default Wide Screen Beige Lilac Rainbow Black & Blue October Send us your theme!

Hark!  The Herald!
Holiday Issue 2016

Wiki Blogs Dicebot

Author Topic: A question! (Programming, Logic and Math)  (Read 651 times)

0 Members and 1 Guest are viewing this topic.

Offline VekseidTopic starter

A question! (Programming, Logic and Math)
« on: December 01, 2007, 11:56:43 AM »
Here's a geek one for you. Why are B trees used instead of binary trees?
« Last Edit: December 03, 2007, 08:16:33 AM by Vekseid »

Offline Sherona

A question! (Programming, Logic and Math)
« Reply #1 on: December 01, 2007, 12:03:45 PM »
*goes all cross-eyed at search results* :P Give me a bit of time,


*takes a stab at it* Ok Technology, and as such anything to do with computer lingo and stuff is just..beyond my ability to understand. Don't ask me why, I just can not seem to wrap my mind around the subject and not for lack of trying.

 A search tree, or binary tree is a structure having two links per node, and it is used to sort items, store them and retrieve them efficiently. Then we have B-Trees, having more than two links per node, commonly used to store information (usually indexes) bigger than the available memory.

Not that I understand more then two words of that, ..spent about three hours trying to read through a bunch of supposed "Simple" basics of trees lol Can't say I didn't attempt :P Hehe was kind of fun to laugh at my own confusion over the matter. :D
« Last Edit: December 01, 2007, 02:16:57 PM by Sherona »

Offline VekseidTopic starter

A question! (Programming, Logic and Math)
« Reply #2 on: December 01, 2007, 08:31:14 PM »
To simplify, imagine looking for a name you know in the phone book. There are multiple ways, if you are playing the role of computer, for doing this.

You could open the phone book in the middle, check to see which half your desired name was in, then cut out the half that was in it. In a balanced binary tree, the halves would be the same size, but in a normal binary tree, this might nit be the same - for example, in a normal binary tree, there may be two million names from N-Z and one million from A-M, but you still end up looking first at the M-N divide because that's where the middle of the alphabetical index is.

When doing a binary search through a normal, unbalanced binary tree, you cut in half each time, so you go from A-Z -> N-Z -> N-Tm -> ... and so on.

Let's say your index has like, 1.9 million names that begin with Sha

Obviously, that's not very efficient, and using binary searches isn't the best that can be done.

Humans look by letters, which amounts to a base-26 tree - We go to S, then H, then A...  this is like a B tree, but not quite, because while a B tree specifies more than two keys per level in a search, a B tree must also be -balanced-.

A balanced search is roughly the equivalent of looking in the exact middle of the phone book, then making a proper quarter, eighth, sixteenth, and so on, until your result is obtained.

In the case of a B-tree of order say... 10, that means it finds the right tenth, then hundredth, then thousandth - obviously a lot faster, especially when you are dealing with billions or even trillions of indexes.

Hope that helps, your question :-p

Offline Sherona

A question! (Programming, Logic and Math)
« Reply #3 on: December 01, 2007, 08:33:58 PM »
*laughs* I will read through that when my head doesn't hurt so much :P

Offline Apple of Eris

A question! (Programming, Logic and Math)
« Reply #4 on: December 01, 2007, 11:13:03 PM »
*blinks* I know that LOOKED like english, heck, I even recognized some of the words, but what they mean... I have no idea.

Thank you Vek for confirming that law and not computer science was the right choice for career.

Offline VekseidTopic starter

A question! (Programming, Logic and Math)
« Reply #5 on: December 01, 2007, 11:32:40 PM »
*blinks* I know that LOOKED like english, heck, I even recognized some of the words, but what they mean... I have no idea.

Thank you Vek for confirming that law and not computer science was the right choice for career.

I wonder the same thing at times, really...

On RPG.net, there is a critique of Exalted: The Fair Folk

"The book is written in a language which appears to be identical to English but is in fact not English!"