B-Trees & R-Trees

Table of Contents

B-Trees & R-Trees

Summary

B-TREES

Motivation

Basic Definitions

Basic Definitions

Basic Definitions

The Basic B-Tree

An Example

Insertion

Insertion

Deletion

Deletion

Cost of operations

Cost of operations

Improvements

Improvements

Improvements

Improvements

B-Trees in multiuser environment

VSAM

R-Trees

Motivation

The Basic R-Tree

The Basic R-Tree

The Basic R-Tree

Definitions & Properties

An Example

An Example

Searching

Inserting

Inserting

Deletion

Updating

Node Splitting

Node Splitting

Node Splitting - Heuristics

Node Splitting - Heuristics

Performance Tests

Conclusion

Email: hcma@cs.umd.edu

Home Page: www.cs.umd.edu/~hcma

Postscript version: rbtrees.ps.gz