B Tree Data Structure Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

B-Tree is a data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic amortized time. B-tree is a generalization of a binary search tree in which a node can have more than two children. It is commonly used in databases and file systems.

Fig 1-1 B-Tree

Above fig 1 is an example of a b-tree whose keys are consonants of English alphabets. An internal node x containing n[x] keys and has n[x] + 1 children. All leaves are at the same depth in a tree. The lightly shaded nodes are examined in a search for the letter R.

Actionscript is a scripting language initially developed by Macromedia but now it is owned by adobe system. The development of websites and software targeting are the main platform for adobe flash. The main executable file for flash is swf file.

OBJECTIVE

Designing an instructional based program for various operation of B-Tree such as insertion, deletion and search using multimedia components like audio, animation, which are presented by using different code in ActionScript 3 flash player

MOTIVATION

The motivation for doing this project was to design a visual instructional based b-tree which would help a laymen understand the concept, which was difficult to understand without multimedia components. Sound effect and animation would allow the user to form a mental picture of the scenario much more easily.

METHODOLOGY

Literature survey formed the main part of work in September. Initially, basic information of B-tree was collected. B-tree itself being a vast topic much time needed to be spent in understanding the concepts which was followed by learning the software adobe flash for another forth night. Since the topic was to make laymen understand the concept of b-tree using the multimedia tools. Its implementation was using action script. For this purpose, Adobe professional CS5 was installed.

Insertion, deletion and searching was the part of the designing of the program and its coding, debugging was done during the month of November. The final touches, summary and report writing was the last phase of the project.

SUMMARY

Action script is scripting languages which help us design various multimedia related components such as animation, audio, video in a two dimensional format. These components are use to perform operation of b-tree such as inserting an element, deleteting a key element and searching for the elements.

BALANCED TREE

HISTORY OF B-TREE

A B-Tree is a dynamic index structure, which is widely used, is a balance tree in which the internal nodes direct the search and the leaf nodes contains the data entries. The tree structure grows and shrinks dynamically it is not feasible to allocate the leaf pages sequentially. They are optimized for situations when part or the entire tree is maintained in secondary storage. A b-tree minimizes the number of disk accesses.

CHARACTERISTIC

Operation like insert, delete on the tree keep it balanced.

A minimum occupancy of 50% is guaranteed for each node except the root.

Deletion is often implemented by simply locating the data entry and removing it, without adjusting the tree.

Searching for a record requires just a traversal from the root to the appropriate leaf.

Length of a path from root to a leaf is known as the height.

Order of the tree is a measure of the capacity of a tree node i.e. d ≤ m ≤ 2d, where d is the order. For root node its 1 ≤ m ≤ 2d.

OPERATION PERFORMED BY B-TREE

There are many types of operations performed by a B-tree some of them are listed below

Search

It is similar to search operation in a binary tree but the only difference is that it makes n-way choice. In this operation the child is selected by performing a linear search of the keys in the nodes.

Initially the greater or equal key value is searched. Once the value is found the child pointer immediately points to the left of the key. Suppose all the keys value are less than the required value then the child pointer points to the right most key. The search is terminated as soon as the searched key is found.

B-tree search is 0(logt n). The running time depends upon the height of the tree.

Figure 2-1 searching a B-Tree for key 21

The above fig 2 is searching a B-Tree for key 21. The tree is of the order d=2. Each node contains between 2 and 4 entries. To search for 21, we follow the third pointer, 20 ≤ 21≤ 30.

Insertion

During insertion first the required node is searched where the value is to be inserted. Once the node is located, the key is inserted into the node. Secondly the node is checked if its full or not, if the required node is full, it should be split to make space for the new key and move the other half of the elements to a separate new node. The parent node should not be full since node move one of the key to the parent node. If the node is full then split the parent node and add the middle key to the node. This process repeat until a parent is found that need not split. If the root splits, then create a new root which has one key and two pointers. The required running time is O (t log n).

Deletion

While deleting an element from a node require special care to make sure that the properties are maintained. While deleting a key if the number of elements in a node reduces to the minimum degree of the tree at that time we have to combine the many nodes and shortened the height of the tree. If the elements have children then they must also be rearranged.

SUMMARY

There are many different kinds of tree in object oriented programming and one among those trees is the balanced tree also known as the B-tree. There nodes have many children and so they are mainly used for disk input and output.

The node x with n[x] keys have n[x]+1 children. They have a balanced height. The insertion and deletion mainly require splitting and merging operations. The running time for a b-tree is h≤logt(n+1)/2 , The root must have 1 key and the internal nodes should at least have t-1 keys but at most 2t-1 keys.

HARDWARE SOFTWARE REQUIREMENTS

The project work is planned to be carried out using a system with the following configuration

HARDWARE

PROCESSOR- Intel Pentium Dual CPU T2390 @1.86GHz 1.87Ghz

Motherboard - Gigabyte P43-ES3G - Intel P43 Chipset +ICH10

RAM -2.00 GB RAM DDR2 1066 MHz

HARD DISK - WESTERN DIGITAL 500 GB SATA

OPTICAL DRIVE - LG SATA 22x DVD-writer

NETWORK CARD - Onboard

Sound Card - Onboard high-definition Audio Driver Version 4.31.2.0

Graphics card - NVIDIA Ge Force 9500 GT-1024 Mb

SOFTWARE

Operating systems - Windows XP SP 2

Office suite - Microsoft Office 2007

Adobe Flash professional CS5

ACTION SCRIPT

It is a scripting language developed by Adobe and has the same syntax and semantics java script. It is targeted mainly for the development of web site with the help of adobe flash player. It is in the form of SWF files.

ACTION SCRIPT 3

This language allows more control and code reusability when building complex Flash applications. It is mainly intended to be compiled and run on a version of the ActionScript Virtual Machine. It is generally targeted for Flash Player 9 and higher version. It executes up to 10 times faster than any other ActionScript code.

ACTION SCRIPT 2

It supports all the standard elements of the ActionScript languages. It lets us write scripts that are closely adhere to standard use in other object oriented languages such as java. It's let us declare the object type of a variable when we create it and provides significantly improved compiler errors.

Features of ActionScript 2.0

The main feature of ActionScript 2.0 is

Familiar object oriented programming model

its implements several object oriented programming (OOP) concepts and keywords such as class, interface and packages similar to java. It provides syntactic formalization of the prototype chaining method used in flash to create objects and establish inheritance.

Strict data typing

it lets us explicitly specify data types for variables, function parameters and function return types.

Compiler warning and errors

help us find bugs in our applications faster.

ACTIONSCRIPT AND FLASH PLAYER

Actionscript is not a case sensitive as long as the publish setting does not use ActionScript 2.0 classes while compiling a SWF executable file.

Data type annotations are enforced at compile time for flash 7 and later if we publish settings set to ActionScript 2.0

DATA TYPE

Object serve as the base class for all class definitions in ActionScript. It's used as associative array that contain key-value pairs, where keys are Strings.

Array may be of any type and values must be cast back to their original type

Vector is dense arrays which may be of fixed-length, and are bounds-checked during retrieval.

Sprite is a display object which is without a timeline.

Movie Clip is an animated clip display object. By default flash timeline is the movie clip.

Bitmap, shapes are both non-animated display object.

Text Field is a dynamic interactive text field object.

Error is an object that allows runtime error reporting when thrown as an exception.

Function is the core class for all Flash.

SUMMARY

ActionScript is basically a language that adds the interactivity to the flash application. It helps in creating both simple and animated SWF files. So far there are three ActionScript versions are formed and once a file is created in the action script class 1.0 it cannot be used by any other class. In the above section some of the features of ActionScript 2.0 are shown and the different types of data types used in flash.

WORKING WITH MOVIE CLIPS

Movie clips are SWF files that run independently and the timeline are part of them. A movie clip can be nested clips; while working with movie clip the parent clip contains more than one child clips. Movie clips can be uniquely created as object to identify them easily and control them in ActionScript. Properties and methods of movie clips class are use to control the appearance and behavior of a clip at a run time. This is the foundation of component based architecture in flash cs3 professional.

CONTROLLING MOVIE CLIPS WITH ACTIONSCRIPT

Global ActionScript function is use to perform tasks on movie clips. Some methods of the movies class perform the same tasks as functions of the same name other function such as hitTest() and swapDepths() don't have corresponding function names.

My_mc.duplicateMovieClip ("new_mc",5);

duplicateMovieClip (my_mc,"new_mc",5)

The above code shows the difference between using a method and using a function. Each instance duplicates the instance my_mc, Name the new clip new_mc, and places it a depth of 5. When a function and method offer similar behavior we can select any one of the movie clip. Only the target timeline should be loaded in flash player when any one of them is called/

the method is activated by using the target path of the instance name with a dot, a method name and last the parameter.

myMovieClip.play(),parentClip.childClip.gotoAndPlay(3);

LOADING AND UNLOADING SWF FILE

The following methods are used 2 open a SWF file without closing a flash player.

The global loadMovie() function method

The loadClip() method

When we load a SWF file we specify a level or movie clip target in which the SWF files loads. While loading a SWF file into a target, the loaded file inherits the properties of the targeted movie clip. Once the flash movie is loaded the properties can be changed.

The unloadMovie() method removes a SWF file loaded by the loadMovie() method. The unloadMovie() make sure there is a smooth transition between SWF files and it decreases the memory which is required by the flash player.

To reuse a clip at a later time, set the_visible property to false and the reset it to true when necessary.

To use loadMovie() the followings steps are used.

Play a sequence of banner

A branching interface is developed with links that select among several SWF files

Build a navigation interface.

SUMMARY

In this chapter we have describe about the movie clips in flash and how they are controlled in ActionScript. Finally how the loading and unloading of a SWF file for movie clip works.

Move clips are self contained SWF files that are run independently and timeline is one of the parts the clip. Flash can uniquely identify a movie clip by giving its instance name. they are objects that easily respond to events, send messages of the other movie clip objects.

WORKING WITH TEXT AND STRING

There is different type of text used in flash and some of them are static text which are used in layouts, dynamic text for longer passages, input text to capture user input, image text for background design, field text.

To display text the best way is to use code and manipulate the strings that appear before they are loaded and displayed it on the stage at the runtime.

The following list describes terminologies used in text and string while using flash

Aliased text don't use color variations to make its jagged edges appear smoother

Anti aliased text use advance aliasing to smooth the text so that the edges of the characters that appear on screen look less jagged. It makes text more legible by aligning text outlines along pixel boundaries.

Characters are letters, numerals and punctuation that combine to make up strings.

Device font are special fonts in flash that are not embedded in a SWF file instead uses whatever font on the local computer that most closely resembles the device font.

TEXT FIELD

The following kind of text field can be created in flash

Static text are use to display characters that do not need to change. They display small amounts of text and also display special fonts.

Dynamic text is use to display characters that are updated and changes at runtime.

Input text: to capture user input

Text component: to display text in the application used, it has an inbuilt scroll bar.

LOADING TEXT AND VARIABLE INTO TEXT FIELD

There are several ways to load a text into a flash document including using flashvars, loadvars, XML or web services. The simplest method of passing text into a flash document is to use the FlashVars property. This passes short strings of text into a flash document through the object and embeds tags in HTML code that you use to embed the SWF file in an HTML page.

Another way to load text into flash document is to use the LoadVars class which load large blocks of text/

XML, web services and flash remoting are the most versatile for loading external data but they are also the most difficult to learn.

SUMMARY

In this session we have discussed about text field and how text and variable are loaded into it. Text field are of four different types mainly they are static, dynamic, input and finally the text component. The simplest way to load a text in a text field is by passing the flash document into the flash var properties.

ANIMATION

FRAME RATE

Frame rate affect the performance of the SWF file and the computer that plays it. Frame rate helps playing the animation smoothly. If an animation set to 12 frames per second in the property inspector plays frames each second. Use the lowest possible frame rate to make the animation appear to play smoothly at runtime, this helps reduce the strain on the end user's processor.

High frame rates puts a lot of stress on the processors and do not change the appearance of the animation at all at runtime. While testing the SWF file check the duration and the size of the animation.

BITMAP

In Flash bitmap caching helps the performance of the non changing movie clips. When the movie is set as the MovieClip.cacheAsBitmap the flash player caches an internal bitmap representation of the movie clip. This improves performance of the movie clips which contain complex vector. All the vector data of a movie clip have a cached which is drawn to the bitmap instead of the main stage. It's ideal to use the cacheAsBitmap property with the movie clips that contain static content and which do not scale or rotate frequently.

DRAWING

The movie clip class are use to draw lines and fill the stage. The drawing tool helps drawing different shapes in the SWF file. With all movie clip masks, strokes are ignored.

SUMMARY

This session describes about animation and the components involved in it such as frame rate, bitmap, and drawing. Code and effect reduces the size of the file which improves the performance and consistency of the animation file. Bitmapping helps the performance of the movie clip. There are various shapes in flash for drawing an animated object in a SWF file.

DESIGNING AND IMPLEMENTATION

INTRODUCTION

Adobe flash player was used in the implementation of the b-tree. An attempt was made in this project to help a laymen understand the concept of a balanced tree various operation. The flash document considered for the implementation of the project contains details of b-tree.

ALGORITHMS

Input

The input is a flash document where different operations in a balanced tree are performed. Some keys elements such as 3, 5, 9, 13, 15, 18, 21, 24, 26, 31, 34, 42, 46, 51, 67, 70, 75, 82, 84, 92, and 96 forms a b-tree structure.

Output

An animation using flash ActionScript 3.0 is been performed, which uses different operations of a balance tree such as insertion, deletion and searching with the given input keys.

INSTALLATION STEP

For this project Adobe flash professional cs5 is been installed. This is an authoring tool used by designers for creating presentation, applications. The flash project includes simple animation explaining the concept of balanced tree. The SWF format is extremely well suited since its files are very small and it has an extensive use of vector graphics. Storage spaces are bitmap graphs which are represented by the mathematical formulas. Bitmap requires a large.

FLASH FILE AND GRAPHICS

For creating a file in a flash firstly a vector graphics is created. This help in designing the elements with the drawing tools and import media elements like audio, video.

Flash work with FLA. File, which has as extension name .fla

Figure 8-1 Screen shot for parts of fla file

The above figure is divided into five main parts.

Stage where the graphics, video, buttons appear during playback.

Timeline: controls the timing of the element which appears in a movie.

Tool panel: holds tools used for selecting objects on the stage and drawing vector graphics.

Properties panel: display edited information of a selected object.

Library panel: where media elements, symbols are stored and organized.

The final step in flash is to create a compressed version of the file created with the extension .swf, this help in playing a file in flash player.

Fla file

Figure 8-2 Screen shot of fla file

The above figure is a screen shot of how a new fla file is created in cs5 using ActionScript 3.0. The file is chosen from the new document dialog box and here the ActionScript 3.0 file type is selected.

Figure 8-3 Screen shot of essential dialog box

In above figure the essential workspace layout option is selected .This step helps in configuring the layout of panels in flash. After this the properties tab is selected to view the stage properties for the file. In the properties tag stage size setting are 550x400 pixels

Drawing

It is a common task in flash and is in the form of vector graph a can be edited at any time. The diagram below shows the steps for creating different patterns. Here we use the oval tool from the tool panel and the stroke color picker decides the color of the shape. The oval tool selection tab helps in drawing the circle on the stage by shifting and drag the shape.

Creating a symbol and adding animation

It is a media asset that are reused anywhere in the document without the need to recreating it again and again. It has images and animations along with other types of content.

Animating shapes

To make a shape work like animation we have to drag the required shape. Here in this project a rectangle is drawn; initially a rectangle shape is select from the drawing tool which is drags to the left of the stage area. Right click is then pressed on the stage and the create motion tween option is chosen from the menu. The timeline automatically appears at the bottom right below the stage.

Figure 8-4 Screen shot of timeline

The above figure shown is the screenshot of the timeline which works for animation of an object. The timeline helps in selecting the frame rate and show how long the required object is suppose to work.

Publishing a file

Once the fla file is ready to publish the flash professional compresses the file into the SWF file format. The publish command automatically generate an HTML file with the correct tags.

Figure 8-5 Screen shot of publishing a file

Compilation

SEARCHING

Figure 8-6 Screen shot of searching in b-tree

In the above figure the screen shot of the searching operation of a b-tree is been shown. Here the key element 82 is to be searched. Since 82 is a greater number therefore the element will directly go to the right most parents where it will see if the element is present.

DELETION

Figure 8-7 Screen shot for deletion

The above figure is the screen shot for deletion operation in a balanced tree. Here the element 31 is to be deleted.

INSERTION

Figure 8-8 Screen shot for insertion

The above figure is screen shot for the insertion operation of the balanced tree. This is the how the b-tree looks after the insertion operation is been performed.

SUMMARY

An instructional b-tree design has been implemented. To carry out the implementation, flash animation was designed using the software adobe flash cs5. The following operation of b-tree such as insertion, deletion and searching are explained through the animation in flash. In this session basic steps in the execution of the project were discussed in detail including the compilation and the execution steps providing screen shots wherever necessary.

FUTURE WORK

The implementation done was carried out considering how to make a laymen understand the concept of B-Tree. The adobe professional cs5 help in implementing the concept of flash. The flash document considered for the project is of simple complexity. But in large scale organization, the flash documents which are used for animation for transaction are of high complexity. Future work can be done to incorporate the animation with high complexity. Also, further work can be done by adding sound effect in the flash animated file thus making a laymen understand the concept more clearly.

LESSONS LEARNT

In the completion of the project, a number of errors came up which were finally solved. The error occurred while file execution. Initially, the timeline for moving one key to the other and adjusting it in the given balanced tree was the problem. This problem was solved by going through the tutorial for flash cs5. Another problem was adjusting the timeline properly and making the animation work perfectly.

CONCLUSION

Study of B-Tree and Audio system using ActionScript in detail. 

Understanding various operations such as searching, insertion, deletion in B-Tree.

Learning of various codes for audio system using the software ActionScript 3

Designing algorithms for various operation of B-Tree.

Implementation of a b-tree.

Compilation of a b-tree.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.