Indexed Sequential ( B+ Tree ) File Structure

Sequence Set

The sequence set is a doubly linked ordered list of data blocks (= physical records).

Each data block contains one or more items (= logical records) ordered by a stored key.

const int MAX_SIZE_BLOCK = ...;

struct BlockItem

{

int key;

Info info;

};

struct Block

{

int prev;

int size; // n in the figures

Block items[MAX_SIZE_BLOCK];

int next;

};

The order of the sequence set is the maximum number of items per data block.

E.g. order = 2

Empty sequence set

Insert { 7, --- }

Insert { 14, --- }

When a data block overflows, it is split in halves.

E.g. Insert { 8, --- }

When a data block becomes less than full ( when an item is being deleted ) then either the block's items are

[1] Redistributed with a sibling data block, or

[2] Merged with a sibling data block.

Exception: If there is only one data block, it can be less than full.

Index

Each index node has the following structure:

const int MAX_SIZE_NODE = ...;

struct NodeItem

{

int key;

int recordNr;

};

struct Node

{

int size; // n in the figures

NodeItem items[MAX_SIZE_NODE];

};

E.g.

Empty B+ tree:

A B+ tree with exactly one data item:

A B+ tree with a small number of data items:

The order of the index is the maximum number of node items per node.

When an index node overflows it is split in halves.

If the root node ( the topmost node ) overflows, it is split in halves AND a new root node is created. The tree increases in height.

When an index node becomes less than full then either

[1] it is redistributed with a sibling node, or

[2] it is merged with a sibling node.

Exception: The root node can be less than full.

Empty B+ tree:

Insert { 7, --- }

Insert { 14, --- }

Insert { 8, --- }

Insert { 3, --- }

Insert { 5, --- }

Insert { 2, --- }