Evolution of tree data structures for indexing • Hacker News Board

Re: Evolution of tree data structures for indexing

#11

Post by bob1029 » Tue, Jul 27, 2021, 5:11 PM UTC

binarybanana wrote: post #10

bob1029 wrote: post #8

No mention of the splay tree? I am a little disappointed. The locality of access and dynamic programming semantics are super compelling to me.

>splay tree Oh yes! Probably my favorite data structure. In the past I've used them instead of arrays for performance (latency) reasons when constructing ordered sets from randomly distributed elements that came in multiple batches. Insertion into a splay tree meant that no sorting step at the end was necessary and the overhead was lower than first collecting everything into an array and only sorting after all elemen…

> The only downside is the possibility of getting into a degenerate state, but that can be avoided by adding some randomness.

If you use GUID keys, this problem magically goes away with zero effort.

Re: Evolution of tree data structures for indexing

#12

Post by infogulch » Tue, Jul 27, 2021, 6:29 PM UTC

j-pb wrote: post #4

phamilton wrote: post #3

Earlier quoted context omitted.

I've wondered similarly. I don't have answers for you, but to add more questions: Are there tree structures that are more amenable to SSDs and the associated write amplification and other perf penalties? Could "hard-linking" in the SSD facilitate covered indexes? Could bitwise operations be performed on the SSD itself? Edit: I found some exploration: https://www.usenix.org/conference/osdi14/technical-sessions/...

We're doing just that. We have an index trie datastructure that is optimized for manipulation by an FPGA in an SSD. Xillinx recently released a product that enables this which it's super awesome and even affordable. https://www.xilinx.com/applications/data-center/computationa...

Very cool! It seems to me that the "disk as a contiguous array of blocks"-paradigm is simply unsuited to SSDs, and ssds have to do a lot of work to support that fiction for the OS and databases in particular. If that's a reasonable assessment, then the next question is: what is a better model/paradigm for cell storage that minimizes bookkeeping overhead?

Re: Evolution of tree data structures for indexing

#13

Post by jandrewrogers » Tue, Jul 27, 2021, 7:35 PM UTC

polyrand wrote: post #6

jandrewrogers wrote: post #5

Earlier quoted context omitted.

There is, but it isn’t what I would call intuitive. Traditional tree-based indexing algorithms embed a diverse set of assumptions about the nature of the hardware that aren’t actually true in modern systems. SSDs are also quasi-sequential devices in important ways that need to be respected for performance reasons. The design problem is that storage density and bandwidth has increased massively and traditional indexin…

I recently started learning about the underlying data structures in databases. What are some examples of those "modern indexing algorithms"?

Most modern indexing structures are in the succinct radix tree algorithm family. This is a diverse algorithm space with many design knobs that can be used to optimize properties and behavior in multiple dimensions, so any two algorithm implementations can look quite different. Most algorithms of this type you see in the wild don't have names, they were designed to fit requirements from first principles.

You can find simple, albeit limited and not too succinct, examples of these types of data structures online. More advanced capabilities crammed into ever more succinct representations can quickly become difficult to reason about -- the code looks much more abstractly information theoretic and less like a traditional index.