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?