An Animation of B-tree Algorithm




Introduction

This is a demonstration flash program to show how B-tree algorithm works like.

Versions

This program works differently by giving a parameter via FlashVars.
This program has three modes.
MANUAL VERSION
This is a version that you can manually add or delete arbitrary elements.
AUTOMATIC VERSION
This is a version that automatically adds and deletes random elements.
This is the version that you see above.
3D VERSION
This version works as a screen-saver like animation.


Configuration

Setting parameter is available. Use FlashVars
example) FlashVars="u=3&l=2&t=3"
Parameters
    u Constant U. The maximum number of elements in a node. Default Value is 3.
    l Constant L. The minimum number of elements in a node. Default Value is 2.
    m Mode ID. Default Value is 1.
        When m=1 it works as Demo Mode 1
        When m=2 it works as Automatic Mode
        When m=3 it works as Demo Mode 2
        When m=4 it works as Manual Mode


Motivation

The purpose that I have written this B-tree algorithm animation is verifying the algorithm of rebalancing after deletion which is described in Wikipedia . As far as I know, There are only few books describe the rebalancing algorithm concretely. For example, in Knuth's book, the deletion algorithm is described with only basic theory and is showed as an exercise for designing algorithms for readers.

There is a very good article of B-tree algorithm with the rebalancing algorithm at Wikipedia. But it does not provide a strict proof and a citation and it is flagged as "citation-needed". This motivates me to write this animation. I practically implement the rebalancing algorithm in the article and it looks working correctly.


Relation about U and L

In the article, the two constant numbers U and L are used. In the article U is defined as a maximum number of elements in a node and L is defined as a minimum number in a node. Though most books including Knuth's book does not use U and L but a constant named "order".

The relation between U and L is discussed at this article . Though the discussion is finished without clear conclusions. This motivates me to let this simulator to set U and L number independently. I still do not know what exactly the relation is. I think L is supposed to be equal or less than floor( U / 2 ) and it is not necessary to be floor( U / 2 ) itself. I think in this way just because I just practically tried with this application. It is without any mathematical proof.


Contact Information


TOP


Copyright(C) 1996-2010 Atsushi Oka