God, I hate how pointless leetcode has become, and how it's used in interviews. Smug assholes using obscure data structures and algorithms trivia that no one ever used at all in any professional setting, and which the interviewer only learned about because he spent a week searching for a coding problem, to decide whether you are competent at putting a button on a window.
Some software jobs involve more than putting a button on a window.
I just wish it was built into languages as one implementation of the list type
Indeed B-trees are hardly novel.
The point is that no one has a practical need to implement them themselves, unless you're working on rolling out your own database engine. If that's the case then either you're doing that for fun or there were steps in the decision process that I'd love to hear the justification.
This is the right data structure to use for collaborative text editing. I made another comment in this thread going in to details. The fastest implementation I know of is Cola, and the author has some great posts going in to details if you’re interested:
An ordered B-Tree iteration would jump between different arrays in the tree often, but a B+ Tree would only have you jump to another array once you’re done iterating over all the elements in the current array.
The following article says the same. https://www.scylladb.com/2021/11/23/the-taming-of-the-b-tree....
Some C & Nim variants are elsethread (https://news.ycombinator.com/item?id=40441832 & https://news.ycombinator.com/user?id=cb321 , respectively).
--
There seems to be a lot of disagreement about how big stdlibs should be. Personally, I think a large Python one was a selling point (batteries included) as well as the way C++ STL and similar Java ones won over many back in the 1990s. However, in today's modern networked-by-assumption world, stdlib maintainers seem to feel overwhelmed pretty easily and eager to "slough off" as much as they can to the ecosystem. It's likely a sub-discussion of an even more broadly contentious "how narrow/wide should dependency trees" be. What seems to be missing, IMO, are agreed upon "metrics" beyond "saleability of the PL/ecosystem".
As guidance for granularity metric relevance, it should be observed that most PL's have some kind of module/separate compilation units. A good answer would be able to work at (and across) many & various levels of the containment hierarchy - at least 3..4 of (procedure, type|module, package, developer, organization). Maybe someone has a set of such metrics in their back pocket, but if so they don't get a lot of exposure in PL chit-chat circles like this one. My guess would be there just isn't enough agreement, but it's probably been fodder for like 100s of software engineering PhD theses. Lol. ( As well as even broader human organization discussions like https://en.wikipedia.org/wiki/Conway's_law )
JavaScript famously implemented arrays in terms of hash tables and.. In a similar vein, I've also known people who also mistakenly thought B-trees could replace a good hash table as the default &| go-to "associative container", but "order costs" (on one side or another) as you said elsewhere.
It's hard to say how much choice needs to be in a stdlib. Hence my exploring how to better say it. :-) E.g., Go has no b-tree in the stdlib, but has a bunch of crypto stuff. Nim has little to no crypto stuff, but has a critbits trie.
EDIT: Oh, and FWIW, at least abc-unix used B-trees for list & tables, not AVL trees.
b-trees can sometimes replace a general hash table as the default associative array type. in part it depends on programming style and other parts of the language; in lisp, for example, the default associative array type was alists (linked lists of key-value pairs) for a long time, and emacs lisp still uses them pretty extensively. and i think you would be hard-pressed to find an sql implementation for which associative arrays are not usually b-trees—in part because in sql you tend to ask questions like 'which values correspond to these 1000 keys?' more often than 'which value corresponds to this key?', and in part for hysterical raisins. (when they wrote system r, oracle, and ingres, main memory was small, so locality of access was more important than it is now.)
I think you're right that requiring such knowledge off the top of one's head and in the context of a one-hour interview is almost always unreasonable, though.
What I'd really want to know is how well a person can do the research to arrive at performant solutions involving, as you say, obscure data structures. In an interview context though, I think you basically just have to ask them - would be nice if you could get a sense of it through doing, though.