Optimal data structure for sorted list 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
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".