search

deadcoders / meetings

Vote on potential topics in this repo's Issues
1 stars 0 forks source link

The Ubiquitous B-Tree (Comer 1979) #3

Closed kubkon closed 10 years ago

kubkon commented 10 years ago

B-Tree is a natural generalisation of the well-known binary search tree data structure. They were designed to work efficiently on secondary storage devices (e.g., HDDs). Many (if not all) databases use B-Tree as the default index data structure. This also includes the leading NoSQL database, mongoDB.

In his paper, Douglas Comer provides a comprehensive survey of B-Tree as well as its variants (B+tree, B*tree, etc.).

I believe that a conceptual understanding of this fascinating topic will be of interest to anyone who is dealing with database systems. At the very least, it should give an idea how database indexes (indices) are organised behind the scenes, and help in grasping the performance constraints when running a query over an indexed table/collection.

jaz303 commented 10 years ago

+1 for this!

kubkon commented 10 years ago

Fixed typos in the author's surname: Cormen -> Comer.