In this Chapter it is mentioned Mongodb Uses B-Tree for Indexes. So i have a question Why it does not use Binary Search Tree because Insertion, deletion, searching of an element is faster in BINARY SEARCH TREE than BINARY TREE due to the ordered characteristics. So Does it Uses BST if no than Why?
Welcome to the community @Vaibhav_Parashar!
It looks you are conflating a B-Tree with a simple Binary Tree: these are not the same data structures.
A B-tree is a self-balancing generalisation of the Binary Search Tree (BST) data structure with better performance characteristics for use cases that work with large amounts of data. B-trees and BSTs have the same average Big-O complexity, but a BST’s worst case complexity for search, insert, and update is O(n)) versus B-tree’s O(log(n)).
The above links include some helpful information on the differences and benefits of these data structures. B-trees are commonly used (and well-suited) for general database and filesystem indexing. There are some variants of B-trees (for example: B-tree category on Wikipedia) and differences in implementation specific to the architecture of different applications, but the high level concepts are similar.
There are also some variations in how B-tree indexes may be used in different products. For example, MongoDB’s WiredTiger storage engine uses prefix compression for index values by default. Prefix compression still stores values in a general B-Tree structure, but reduces some of the repetitive details for more efficient index size. For an older (but still applicable) overview, see WiredTiger - how to reduce your MongoDB hosting costs.
B-trees are ordered, and the order of keys is important if you want to efficiently use an index to sort query results.
Regards,
Stennie
2 Likes
This topic was automatically closed 5 days after the last reply. New replies are no longer allowed.