This is non-intuitive to me. I'd expect that the natural SIMD-extension to a binary search tree would be a 4-BTree (assuming 4-elements compared per SIMD unit)

This is non-intuitive to me. I'd expect that the natural SIMD-extension to a binary search tree would be a 4-BTree (assuming 4-elements compared per SIMD unit). For AVX512, I'd expect a 16-BTree to be used. ---------- EDIT: > The paper mentionned at the beginning, propose to have a binary tree layed out like the following: > And if you take time to understand how this maps back to the binary tree, you will notice that we are storing parent-children triangles. With this, we can now apply SIMD operations on both the parent and the children in order to either dtermine if the data we are looking for is in the triangle, or if we should continue our search. Hmmmmmmm. So maybe they are making a B-Tree here except not calling it one?