https://stackoverflow.com/questions/22125233
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianAll three of these structures are implementations of ordered dictionaries - they maintain a set while efficiently supporting insertions, deletions, lookups, successors, and predecessor queries.
Binary search trees and 2-3 trees differ from B-trees in that BSTs and 2-3 trees are (usually) main-memory data structures while B-trees are (usually) external memory data structures. Specifically, B-trees are designed to be stored on disks in which the cost of reading or writing a disk page is significantly higher than the cost of performing simple computations. If you're planning on storing a huge volume of data that can't fit into main memory, B-trees are an excellent choice for a data structure. On the other hand, in main memory, B-trees with a very large branching factor will be slower than BSTs or 2-3 trees because each B-tree insertion or deletion can require a large number of pointer reassignments. For data sets that do fit into main memory, 2-3 trees and BSTs are usually a superior choice (though there has been some research showing that low-order B-trees can outperform BSTs in main memory due to cache effects.)
As for BSTs and 2-3 trees: the "binary search tree" is not a single data structure. There are pure BSTs with no balancing, red/black trees, AVL trees, AA trees, splay trees, treaps, scapegoat trees, weight-balanced trees, RAVL trees, etc. Each of these data structures attempts to balance the BST using some rules so that lookups, insertions, and deletions are fast. The 2-3 tree is a variation on a BST that allows for multiple keys per node in order to give simple rules for maintaining balance. The question typically wouldn't be "when is a BST better than a 2-3 tree or vice-versa" as much as "what advantages does a 2-3 tree have over other balanced BSTs and vice-versa," and that's something that you'd have to figure out through profiling.
Hope this helps!
