I want to estimate how many reads the Partial index of PostgreSQL with the method B-tree requires, since I have not been able directly to alter the block size. PostgreSQL manual about the index here and here about the block size, which is 100 for aux so having 3 reads.

The default memory taken by the block size is 8 KB i.e. 1 block normally but I am not sure if this can be possible because log_1(2) is infinity. I got the idea that the number of reads is dynamically calculated possibly also in PostgreSQL here by considering B-tree where the block size determines the number of reads. I would like to know how much this is in the block size: log_b n where b is the block size and n is the number of events. I think it cannot be one mathematically. I think Postgres B-tree is implemented the standard way as described in the Wiki page, also described by Cormen et al.

B-tree index contains only keys in PostgreSQL, based on this answer. Data is then again in tables which are logical heaps. The point of indexes is to store keys to begin with. Data lies in tables, which are logical heaps, based on here. I am interested in how PostgresSQL make the entity called B-tree. Based on here, the physical storage of B-tree indexes and tables are using the same data pages with mostly the same page-layout. However, I am interested in how this entity works together. Probably, the functioning of the index and data can be described by this:

B-tree grows from root, not from leaves.

but more precisely from Sumathi about Fundamentals of Relational Database Management Systems (Studies in Computational Intelligence):

In B-tree, nonleaf nodes are larger than leaf nodes. Pointers to data records exist at all level of the tree.

In B+tree, pointers exists only at the leaves. How can you evalute the pointer system of B-tree? How can you describe the big-O space taken by PostgreSQL B-tree? How does Postgres make its B-tree index?


1 Answer 1



The PostgreSQL B-Tree index is very strongly based on the implementation by Lehman and Yao, which includes a lot of work oriented around multi-version concurrency control, but there's still great info in this paper.

Of course, PostgreSQL doesn't make a 100% accurate replica of the method in the paper, and to find the differences, there will be almost no way to do it other than to (1) find someone who understands the PostgreSQL B-Tree, and has the time to go through the intricate explanation, or (2) dig through the source code yourself.

Another possibility is for you to visit Bruce Momjian's excellent reference website, where he discusses PostgreSQL internals in more detail.

In this case, however, based on the nature of your questions, I feel like you may have a fundamental misunderstanding about how B-Tree indexes work. In this case, I think a little Google searching, or maybe reading through a portion of a textbook like Fundamentals of Database Systems by Elmasri & Navathe would do you some good.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.