5 ms·

> "Scale of data often works against you, and balanced trees are the first tool in your arsenal against it." An ironic caveat to this is that balanced trees do

> "Scale of data often works against you, and balanced trees are the first tool in your arsenal against it." An ironic caveat to this is that balanced trees don't scale well, only offering good performance across a relatively narrow range of data size. This is a side-effect of being "balanced", which necessarily limits both compactness and concurrency. That said, concurrent B+trees are an absolute classic and provide important historical context for the tradeoffs inherent in indexing. Modern hardware has evolved to the point where B+trees will often offer disappointing results, so their use in indexing has dwindled with time.

hashmash 4y ago
What kinds of indexing structures are used instead, and how do they differ from B+trees? Do you have examples of which relational databases have replaced B+tree indexes?
- xmprt 4y ago
  I know Clickhouse uses MergeTrees which are different from B+trees. However it can't really be used as an RDBMS. It's especially bad at point reads. https://en.wikipedia.org/wiki/Log-structured_merge-tree https://en.wikipedia.org/wiki/Log-structured_merge-tree
  - mikeklaas 4y ago
    There are projects that use LSMTs as the storage engine for RDBMS' (like RocksDB); I'm not sure it's accurate to say "they can't be use as an RDMBS".
    - petergeoghegan 4y ago
      It's definitely possible, and can make a lot of sense -- MyRocks/RocksDB for MySQL seems like an interesting and well designed system to me. It is fairly natural to compare MyRocks to InnoDB, since they're both MySQL storage engines. That kind of comparison is usually far more useful than an abstract comparison that ignores the practicalities of concurrency control and recovery. The fact that MyRocks doesn't use B+Trees seems like half the story. Less than half, even. The really important difference between MyRocks and InnoDB is that MyRocks uses log-structured storage (one LSM tree for everything), while InnoDB uses a traditional write-ahead log with checkpoints, and with logical UNDO. There are multiple dimensions to optimize here, not just a single dimension. Focusing only on time/speed is much too reductive. In fact, Facebook themselves have said that they didn't set out to improve performance as such by adopting MyRocks. The actual goal was price/performance, particularly better write amplification and space amplification.
    - xmprt 4y ago
      I should have clarified that I meant Clickhouse can't really be used as an RDBMS. I wasn't aware that RocksDB uses LSMTs.
- jandrewrogers 4y ago
  The property being optimized for, relative to B+trees, is extreme compactness of representation. In the pantheon of possible indexing algorithms, B+trees are pretty far on the bloated end of the spectrum in terms of the ratio between data space and index space. All indexes have a scaling performance cliff due to the index structure filling up and eventually overflowing available cache, crowding out the data and forcing page faults for almost every index write. In B+tree indexes this happens relatively early and often. Radically improving index compactness is achieved by loosening design constraints on B+trees: the indexes represent a partial order which only converges on a total order at the limit and the search structure is unbalanced. In the abstract these appear slightly less efficient but it enables the use of selectivity-maximizing succinct representations of the key space that can get pretty close to the information theoretic limits. Scalability gains result from the radical reduction in cache footprint when represented this way. Optimal compressive indexes are not computable (being equivalent to AI), so the efficient approximation strategies people come up with tend to be diverse, colorful, and sometimes impractical. Tangentially, some flavors have excellent write performance. It is not a trivial algorithm problem but there are a few design families that generalize well to real databases engines. I wouldn't describe this as a fully solved problem but many ordinary cases are covered. There isn't much incentive to design a relational database engine that can use these types of indexes, since the types of workloads and data models that recommend them usually aren't relational. Someone could, there just isn't much incentive. It is more de rigueur for graph, spatiotemporal, and some types of analytical databases, where there is no other practical option if scalability matters at all.
- analyst74 4y ago
  Databases designed to query large amounts of data tend to rely on partition key to allow parallel workloads (i.e. map reduce). And this partition data is stored like hash index. Big query would be one example.
petergeoghegan 4y ago
> Modern hardware has evolved to the point where B+trees will often offer disappointing results, so their use in indexing has dwindled with time. This is pure nonsense. B+Trees are used extensively and by default by 5 out of 5 of the top database systems, according to db-engines.com.
- jandrewrogers 4y ago
  You don't actually address the point. If your database engine is an old design or your data is small by modern standards, then a B+tree will be one of the few indexing algorithms available and if the data is small it will probably work. Modern database kernels targeting modern hardware and storage densities typically aren't using B+trees and the reasons why are well-understood. No one with any sense is using a B+tree to index e.g. a trillion records, which is a pretty ordinary thing to do on a single server in 2022. You can't just swap out indexing architectures due to their dependency on storage engine and scheduling behavior, so older databases like PostgreSQL will be using B+trees for the indefinite future even if suboptimal. The transition away from B+tree based architectures in new databases engines started about 10-15 years ago. Back then I used them ubiquitously but I honestly don't remember the last time I've seen one in a new design.
  - petergeoghegan 4y ago
    > You don't actually address the point. You said that B-Trees "use in indexing has dwindled with time". This is demonstrably false. > Back then I used them ubiquitously but I honestly don't remember the last time I've seen one in a new design. Even if that was true (which it definitely isn't), why would anybody judge the commercial or scientific relevance of B-Trees by looking at what new systems do? There are very few new systems that are intended to be competitive as general purpose systems, which is where most of the market is. You still haven't actually named a single example of a "modern database kernel" that exemplifies what you're talking about.
    - heisjustsosmart 4y ago
      Read this guy's past posts, you will save yourself a lot of time. He does a lot of this sort of thing.
ddorian43 4y ago
You never post anything constructive. Just that everything in open source sucks while you do fancy algorithms in your basement with spatial data at the boring facility. Anytime anybody asks for more you never reply with something constructive or link to a paper/algorithm or something. The maximum you've told is "yeah do what scylladb does but you will still suck". It just feels as advertisement and doesn't really add anything to the discussion I believe. All your comments are the same in all database threads. endrant

hashmash 4y ago

What kinds of indexing structures are used instead, and how do they differ from B+trees? Do you have examples of which relational databases have replaced B+tree indexes?

xmprt 4y ago
I know Clickhouse uses MergeTrees which are different from B+trees. However it can't really be used as an RDBMS. It's especially bad at point reads. https://en.wikipedia.org/wiki/Log-structured_merge-tree https://en.wikipedia.org/wiki/Log-structured_merge-tree
- mikeklaas 4y ago
  There are projects that use LSMTs as the storage engine for RDBMS' (like RocksDB); I'm not sure it's accurate to say "they can't be use as an RDMBS".
  - petergeoghegan 4y ago
    It's definitely possible, and can make a lot of sense -- MyRocks/RocksDB for MySQL seems like an interesting and well designed system to me. It is fairly natural to compare MyRocks to InnoDB, since they're both MySQL storage engines. That kind of comparison is usually far more useful than an abstract comparison that ignores the practicalities of concurrency control and recovery. The fact that MyRocks doesn't use B+Trees seems like half the story. Less than half, even. The really important difference between MyRocks and InnoDB is that MyRocks uses log-structured storage (one LSM tree for everything), while InnoDB uses a traditional write-ahead log with checkpoints, and with logical UNDO. There are multiple dimensions to optimize here, not just a single dimension. Focusing only on time/speed is much too reductive. In fact, Facebook themselves have said that they didn't set out to improve performance as such by adopting MyRocks. The actual goal was price/performance, particularly better write amplification and space amplification.
  - xmprt 4y ago
    I should have clarified that I meant Clickhouse can't really be used as an RDBMS. I wasn't aware that RocksDB uses LSMTs.
jandrewrogers 4y ago
The property being optimized for, relative to B+trees, is extreme compactness of representation. In the pantheon of possible indexing algorithms, B+trees are pretty far on the bloated end of the spectrum in terms of the ratio between data space and index space. All indexes have a scaling performance cliff due to the index structure filling up and eventually overflowing available cache, crowding out the data and forcing page faults for almost every index write. In B+tree indexes this happens relatively early and often. Radically improving index compactness is achieved by loosening design constraints on B+trees: the indexes represent a partial order which only converges on a total order at the limit and the search structure is unbalanced. In the abstract these appear slightly less efficient but it enables the use of selectivity-maximizing succinct representations of the key space that can get pretty close to the information theoretic limits. Scalability gains result from the radical reduction in cache footprint when represented this way. Optimal compressive indexes are not computable (being equivalent to AI), so the efficient approximation strategies people come up with tend to be diverse, colorful, and sometimes impractical. Tangentially, some flavors have excellent write performance. It is not a trivial algorithm problem but there are a few design families that generalize well to real databases engines. I wouldn't describe this as a fully solved problem but many ordinary cases are covered. There isn't much incentive to design a relational database engine that can use these types of indexes, since the types of workloads and data models that recommend them usually aren't relational. Someone could, there just isn't much incentive. It is more de rigueur for graph, spatiotemporal, and some types of analytical databases, where there is no other practical option if scalability matters at all.
analyst74 4y ago
Databases designed to query large amounts of data tend to rely on partition key to allow parallel workloads (i.e. map reduce). And this partition data is stored like hash index. Big query would be one example.

petergeoghegan 4y ago

> Modern hardware has evolved to the point where B+trees will often offer disappointing results, so their use in indexing has dwindled with time. This is pure nonsense. B+Trees are used extensively and by default by 5 out of 5 of the top database systems, according to db-engines.com.

jandrewrogers 4y ago
You don't actually address the point. If your database engine is an old design or your data is small by modern standards, then a B+tree will be one of the few indexing algorithms available and if the data is small it will probably work. Modern database kernels targeting modern hardware and storage densities typically aren't using B+trees and the reasons why are well-understood. No one with any sense is using a B+tree to index e.g. a trillion records, which is a pretty ordinary thing to do on a single server in 2022. You can't just swap out indexing architectures due to their dependency on storage engine and scheduling behavior, so older databases like PostgreSQL will be using B+trees for the indefinite future even if suboptimal. The transition away from B+tree based architectures in new databases engines started about 10-15 years ago. Back then I used them ubiquitously but I honestly don't remember the last time I've seen one in a new design.
- petergeoghegan 4y ago
  > You don't actually address the point. You said that B-Trees "use in indexing has dwindled with time". This is demonstrably false. > Back then I used them ubiquitously but I honestly don't remember the last time I've seen one in a new design. Even if that was true (which it definitely isn't), why would anybody judge the commercial or scientific relevance of B-Trees by looking at what new systems do? There are very few new systems that are intended to be competitive as general purpose systems, which is where most of the market is. You still haven't actually named a single example of a "modern database kernel" that exemplifies what you're talking about.
  - heisjustsosmart 4y ago
    Read this guy's past posts, you will save yourself a lot of time. He does a lot of this sort of thing.

ddorian43 4y ago

You never post anything constructive. Just that everything in open source sucks while you do fancy algorithms in your basement with spatial data at the boring facility. Anytime anybody asks for more you never reply with something constructive or link to a paper/algorithm or something. The maximum you've told is "yeah do what scylladb does but you will still suck". It just feels as advertisement and doesn't really add anything to the discussion I believe. All your comments are the same in all database threads. endrant