0
$\begingroup$

Most of the resources on the web I have encountered say that "sorted arrays and other sorted data structures are implemented with binary search trees (BSTs)".

Even though B-trees are a generalization of BSTs, I have not seen much of anything say they are used to create ordered data structures. Wondering if programming languages could/should B-plus trees to create a sorted array, or does it use BSTs. So part of the question is, can B-trees, and B-plus trees be used to create associative arrays and sorted arrays and other list data structures (or should they). The other part of the question is which data structure is optimal for all three sorted list operations (search, insert, delete).

I have heard of skip lists as well, but don't understand them yet. I haven't implemented any sort of BST so I don't have a great deal of knowledge about them but I roughly understand how they work. I have read B-plus trees are best for disk storage solutions (not sure exactly why) because high fanout / low depth. But I am more wondering for purely in-memory sorted arrays, what is the optimal data structure for maintaining it:

  • Binary Search Tree
  • Red-Black Tree
  • B-Tree
  • B-Plus Tree
  • Skip list
  • Other
$\endgroup$
  • 2
    $\begingroup$ B-trees are preferred on disk because disk I/O operations are performed in blocks, so that larger tree nodes are preferred. For in-memory operation, this is unnecessary (except maybe for cache effects). AVL or Red-Black trees are good candidates. $\endgroup$ – Yves Daoust Apr 25 '18 at 14:45
3
$\begingroup$

Yes, B-trees and B+ trees can be used to create a sorted array or other ordered data structure.

There is no one data structure that we can call "optimal". There are a variety of data structures that have various tradeoffs. Their performance has some similarities, and which one you choose depends on the specific situation (whether you want an in-memory data structure or an on-disk data structure, how important ease of programming is, how important worst-case vs average-case performance is, and many other considerations). So, I would be reluctant to pick any one of them as "optimal".

$\endgroup$
  • $\begingroup$ Would like to know if it is better to use B+trees than the others for in-memory access if possible. For example, saw this github.com/attaswift/BTree which implements sorted lists. Since it's new / Swift, maybe B-trees were a better choice than RB or BSTs, maybe now B+trees are even better. (For in-memory stuff). Just speculating as to why they went with that approach. $\endgroup$ – Lance Pollard Apr 25 '18 at 16:13
  • $\begingroup$ "Due to the coarse granularity of data accesses and the heavy use of latches, indices in the B-tree family are not efficient for in-memory databases, especially in the context of today’s multi-core architecture." arxiv.org/pdf/1601.00159.pdf $\endgroup$ – Lance Pollard Apr 26 '18 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.