4 ms·
Take a look at ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING. TL;DR there are schemes like this called "Eytzinger" and "van Emde Boas". https://arxiv.org/ftp/a
by macdice 8y ago
Take a look at ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING. TL;DR there are schemes like this called "Eytzinger" and "van Emde Boas".
https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf
The topic of arranging keys like this within index pages (or maybe elsewhere) has come up on the pgsql-hackers mailing list before:
https://www.postgresql.org/message-id/flat/3B774C9E-01E8-46A7-9642-7830DC1108F1%40yandex-team.ru https://www.postgresql.org/message-id/flat/3B774C9E-01E8-46A...