Datastructures used in DBMS

Question

What are the datastructure used in DBMS like Oracle,MySQL & Sqlite for storing and retrieving records.

Answer 1

Usually a clever implementation of B-Trees

From the above linked wikipedia article:

A B-tree of order m (the maximum number of children for each node) is a tree which satisfies the following properties:

1. Every node has at most m children.
2. Every node (except root and leaves) has at least m⁄2 children.
3. The root has at least two children if it is not a leaf node.
4. All leaves appear in the same level, and carry information.
5. A non-leaf node with k children contains k–1 keys

The advantages of which are that data can be accessed in logarithmic time, as with most search trees (such as standard binary trees), but the timing properties are better in the average case.

Answer 2

MySQL has pluggable storage systems. That means that engine can use different storages. It currently has 5-6 of them that you can use. And since it's open source, you can see how it is done.

SQLite uses it's own B-Tree implementation with journaling. Open source - you can look at it.

Firebird and Interbase are using B-Trees with multi-record versioning systems for storage. Firebird is open source. Worth looking.

Can't tell for Oracle, MS SQL Server or other proprietary database systems, since they keep storage information secret.