# Read nodes of a BST in blocks of size $k$ and traverse it in $\mathcal{O}(log_kn)$

This describes how one can neatly store a binary search tree as an array. I'm looking for a way to store a BST that will allow me to traverse any root to leaf path by loading $\mathcal{O}(log_kn)$ blocks. I call a bunch of nodes a block, the blocks are of size $k$.

My goal is to store a perfectly balanced binary search tree with $n$ nodes as an array and be able to traverse any root to leaf path in a small number of steps. To achieve this I want to read blocks of $k$ elements and upon seeing those $k$ elements I should be able to decide where in the array I need to read the next $k$ elements from. I want to repeatedly read $k$ elements and traverse from root to leaf node in such a way that everytime I read $k$ elements I know where to move next inside of the array. A larger $k$ would mean more "branches" and a smaller number of steps. This sounds like a B-tree to me.

I want to store a perfectly balanced binary search tree as an array but in such a way that I can traverse any root to leaf path by loading $\mathcal{O}(log_kn)$ blocks.

Such an approach minimizes the number of blocks read and can be used to minimize memory accesses which is my final goal.

Does anyone have any resources where I could learn more about or how could I approach this?

• I'm not sure asking for recommendations on resources, books, tutorials, etc. is on-topic here. Also, doesn't the fact that you can go from root node at position $i$ to child node at positions $2i$ and $2i + 1$ already give you the paths you're looking for? I'm not sure if I'm following what you're trying to get at. – code_dredd Oct 9 '17 at 9:12
• Usually, in asymtotics, base of logarithm is excluded (since it does not make sence). – rus9384 Oct 9 '17 at 9:14