A question! (Programming, Logic and Math)

[Vekseid]

Here's a geek one for you. Why are B trees used instead of binary trees?

[Sherona]

*goes all cross-eyed at search results* 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 Hehe was kind of fun to laugh at my own confusion over the matter.

[Vekseid]

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

[Sherona]

*laughs* I will read through that when my head doesn't hurt so much

[Apple of Eris]

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

[Vekseid]

*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!"