Page 175 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms Mandeep Kaur, Lovely Professional University

Notes Unit 8: B-trees

CONTENTS

Objectives
Introduction
8.1 B-trees
8.2 Structure of B-trees

8.3 Height of B-trees
8.4 Operations on B-trees
8.5 Inserting a New Item
8.6 B-tree-Deleting an Item
8.7 B-tree Algorithms
8.8 Applications

8. 9 Summary
8.10 Keywords
8.11 Self Assessment
8.12 Review Questions

8.13 Further Readings
Objectives

After studying this unit, you will be able to:
Explain the concept of B-trees
Describe B-trees algorithms

Introduction

The key factors which have been discussed in this unit about the b-trees in data structures. While
dealing with many problems in computer science, engineering and many other disciplines, it is
needed to impose a hierarchical structure on a collection of data items. For example, we need
to impose a hierarchical structure on a collection of data items while preparing organizational
charts and genealogies, to represent the syntactic structure of source programs in compilers.

A B-tree is a tree data structure that keeps data sorted and allows insertions and deletions that is

logarithmically proportional to file size. It is commonly used in databases and fi le systems.
8.1 B-trees

In B-trees, internal nodes can have a variable number of child nodes within some pre-defi ned
range. When data is inserted or removed from a node, its number of child nodes changes. In

order to maintain the pre-defined range, internal nodes may be joined or split. Because a range
of child nodes is permitted, B-trees do not need re-balancing as frequently as other self balancing

170 LOVELY PROFESSIONAL UNIVERSITY