B Tree

UNIVERSITE AKLI MOHAND OULHADJ – BOUIRA –
Faculté des sciences et des sciences appliquées

Département de Informatique
TP SDA ( B-TREE REPORT )
Realized by:
YAHOUI SOHEIB
NCERBEY SARA
KAHLOUCHE NOURELHOUDA
1
 Table of contents ................................................................................................... 2
 Introduction ............................................................................................................ 3
 Main functions .............................................................................................................3
Insertion .....................................................................................................................3
Removing ............................................................................................................... 7
Searching .......................................................................................................... 10
Traversal ........................................................................................................ 10
 Test ................................................................................................................................11
 Conclusion ................................................................................................................. 13
2
1) Introduction:
A B-tree is a self-balancing tree data structure that maintains sorted data and
allows searches, sequential access, insertions, and deletions in logarithmic
time. The B-tree generalizes the binary search tree, allowing for nodes with
more than two children.
IN our project we will implement the b-tree of order 2 with a “ c “ code

source . our work contains these main functions :
1-insertion into the tree
2- deleting
3-searching
4- print the value of all the tree (traversal the tree).
2) Main functions :
2-1) the insertion:
Max = 5 , is the number of maximum pointers in one node which means 4
values .
Min = 3 , is the number of minimum pointers in one node which means
2 values
“order 2”
We can allow the user to choose the max and min ( a b-tree with
customizable order )
3
this function it allows us to create a new node , then we have to know
where to place this value into the node (her position in the node ) . for now ,
we suppose that we have no overflow in the node (we don’t need to split it ).
4
In case of we need to split the node which means we have passed the
maximum pointers allowed ,for this we have created this function
This function links the child node with parent node and initialize her
variables ..
But To insert a value into a node we may split or we may not

In order to know we will use this function , which return 1 if we have to split
and split the node , otherwise it will use precedent function and add the
value . the function is this below :
5
The duplicates are not allowed .
Finally , the insert function we use all these function that seen before ,
It will run the function (set value in node) if it returns 1 than it call to the
function (create new node)
6
2-2) deleting a value :
the problem when we remove a value from a node that we will have a
number of keys inferior than 2 which is not allowed in our b –tree (order 2)
first we have supposed a case when the number of keys is bigger than 2 and
we created a function which remove a value from a node and rearrange the
values
There is cases (underflow ) when we remove we need to down parent node

with the left or right children therefore we have created these 2 function
functions
7
And also in other cases we need to merge the nodes with each other
8
This function uses all the precedent functions , in order to delete a value
from a node it test which case we are and adjust the result , we test the
number of keys in node (count) with min and max
9
2-3) search a value in a b-tree :
This function print the value if it exists . else , it will return nothing
2-4) traversal the tree :

In order to print all the values of the tree We generate a function which
traverse all the tree .
10
3) test :
In order to test our functions we run them into a program in the main
function and give the user the choice to choose what to do . like this :
11
A simple demonstration :
12
4) conclusion : we have implemented the b tree in c language , b tree of
order 2 , we could simply make it customizable by letting the users choosing
the values of max and min .
13

B Tree

Uploaded by

Copyright:

Available Formats

B Tree

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

B Tree

Uploaded by

Copyright:

Available Formats

UNIVERSITE AKLI MOHAND OULHADJ – BOUIRA –

Faculté des sciences et des sciences appliquées

TP SDA ( B-TREE REPORT )

 Main functions .............................................................................................................3

IN our project we will implement the b-tree of order 2 with a “ c “ code

But To insert a value into a node we may split or we may not

There is cases (underflow ) when we remove we need to down parent node

2-4) traversal the tree :

You might also like