3

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?

  • 2
    I'm not real clear on what you're asking here: is your question about the BLOCKSIZE compile-time constant, which you can set via ./configure --with-blocksize=BLOCKSIZE ... and defaults to 8 KB? – Josh Kupershmidt Aug 19 '15 at 20:09
  • 1
    1 block = 8 KB, in the default configuration of PostgreSQL. – Chris Aug 19 '15 at 20:17
  • 2
    log_1(2) has nothing to do with the block size. Postgres uses an 8kb block size. That's it. Nothing more, no formulas, no magic, no nothing. One block is 8kb there is nothing more to it. Where do you get the idea that the blocksize is (dynamically) calculated using log_1(2)? – a_horse_with_no_name Aug 19 '15 at 22:21
  • 3
    The block size is the same for all tables and indexes. – Erwin Brandstetter Aug 20 '15 at 3:57
  • 2
    @ErwinBrandstetter already answered something like this last year : stackoverflow.com/questions/25004505/b-tree-or-b-tree/… – RolandoMySQLDBA Aug 20 '15 at 18:15
6

Masi,

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.

  • Pointers to the data records exist at all levels of the B-tree. I am evaluating this. – Léo Léopold Hertz 준영 Aug 20 '15 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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