Quote:
|
Originally Posted by alexander
So what is so special about the Reiser that i call revolutionary? well its not just simple trees that i am referring to, the guy created a datastructure that he called a dancing tree. Its crasy even in concept, its a tree that ballances itself to optimize the search though itself...
|
Implementations of balanced b-trees were considered pretty revolutionary
back around 1973, when the MUMPS programming language and various close cousins were first being ironed out.
I encountered them in 1985, by which time there were only a few significant variations on the 1977 ANSI language standard, and was duly awed and impressed. Rather than my usual cultish rant about its virtues, here’s a
link to a previous ranting post.
In the days were a GB of storage was consider high-end, most were impressed by MUMPS’s access speed. These days, most are impressed by its data scalability. A typical database has 10-20 logical nodes per physical block, so a typical 6-level, 50 GB database scales to 20 TB with an increase in cached or uncached retrieve speed of only 33%. As you might expect from a 30-year-old technology, nearly all implementation of M are very solid.
Balanced b-trees do indeed implement awesome database. They’re not, however, very new. Though, I must admit “dancing trees” is a way catchier name than [Maxi-]M[UMPS][-tech], MIIS, Cache, or any of the names for this old technology, this after a big, international contest to come up with a catchier name for the 1995 language standard. The winner: “M”.
