1

The B-Tree and the R-Tree are two similar index structures that PostgreSQL offers in its implementation.

Both structures can have at most m children per node and as other tree structures, children can have other children. However, in my test data, my structures are always in the form of a root node with many children i.e. just 2 levels.

How can I understand better at which point will the structure's depth increase? What determines how many elements can be on the same level of a tree in terms of PostgreSQL? Is it possible to configure these or the m variable?

closed as unclear what you're asking by Evan Carroll, LowlyDBA, Erik Darling, Mr.Brownstone, McNets Feb 6 '18 at 8:44

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • I wonder why you think you need that information? What is the problem you are trying to solve? – a_horse_with_no_name Feb 5 '18 at 10:05
  • I am just a curious person and want to understand the nature of these indexes in a practical application. – Zeruno Feb 5 '18 at 22:38
0

Both structures can have at most m children per node and as other tree structures, children can have other children.

The million dollar question there is what you mean when you say m children. Math and algorithms in the abstract are concerned with purity: the name for that structure is a Binary Search Trees. Databases are concerned with concurrency and performance, they don't use Binary Search Trees (usually). PostgreSQL implementation of a B-tree isn't based on "children" but on index tuple size and fill factors. Simply, if you can fit more items on the page, you do that: it's called the Index Blocking Factor. The structure is called a B-Tree. Every level of the tree requires a block seek, so you want to do the most you can do to minimize the amount of blocks you must retrieve to complete the index operations. Further complicating matters, the size of the index tuple is variable, from the docs,

Lehman and Yao assume fixed-size keys, but we must deal with variable-size keys. Therefore there is not a fixed maximum number of keys per page; we just stuff in as many as will fit. When we split a page, we try to equalize the number of bytes, not items, assigned to each of the resulting pages. Note we must include the incoming item in this calculation, otherwise it is possible to find that the incoming item doesn't fit on the split page where it needs to go!

tldr; you have little control of the depth (outside of fillfactor). The rows being indexed can result in a variable page size entry, and the depth is a factor of your block size and the index entry size.

  • In the case of R-Tree, if you try to stuff an item in a page and it doesn't fit, a new page is created and the overflowing items are distributed over two splits (that which overflowed and the new one) on the same level. What I am trying to know is, in the R-Tree example, how long can this process keep going on before depth is increased instead of making a new page on the same level? I hope it is a bit clearer this way. – Zeruno Feb 5 '18 at 0:19
  • "the overflowing items are distributed over two splits" I don't believe that to be true. I don't think you can overflow from one page to another. But, you'll have to reference the source. You split generating a totally new page with half the page size of the previous page. – Evan Carroll Feb 5 '18 at 0:22
  • Sorry for the typo, I meant to say "distributed over two pages ... using a splitting/distribution technique". This is something clearly stated in Guttman's original 1984 R-Tree paper and I believe in the PostgreSQL source code, too. Do you still feel it necessary that I reference a source? – Zeruno Feb 5 '18 at 0:27
  • Yes. Namely the PostgreSQL source. – Evan Carroll Feb 5 '18 at 0:28
  • @Zeruno you can see it working here, github.com/postgres/postgres/blob/… – Evan Carroll Feb 5 '18 at 0:30

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