Shulou(Shulou.com)05/31 Report--

This article mainly explains the "PostgreSQL database B-Tree index physical storage structure is how", the article explains the content is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in-depth, together to study and learn "PostgreSQL database B-Tree index physical storage structure is how" it!

1. Test data

We continue to use the test data used in the previous section, this time by inserting more than 1000 rows of data.

For easy comparison, check the index metadata page testdb=# select * from bt_metap ('pk_t_index') before inserting data. Magic | version | root | level | fastroot | fastlevel | oldest_xact | last_cleanup_num_tuples-+-340322 | | 3 | 1 | 0 | 1 | 0 | 0 |-1 (1 row) testdb=# do $$testdb$# begintestdb$# for i in 19. 1020 looptestdb$# insert into t_index (id) | C1, c2) values (I,'#'| | I | |'#','#'| | I | |'#') Testdb$# end loop;testdb$# end $; DOtestdb=# select count (*) from tasking index; count-1008 (1 row) II. Index storage structure

After inserting the data, re-view the index metadata page information:

Testdb=# select * from bt_metap ('pk_t_index') Magic | version | root | level | fastroot | fastlevel | oldest_xact | last_cleanup_num_tuples-+-340322 | | 3 | 3 | 1 | 3 | 1 | 0 |-1 (1 row) |

Root block changes from block 1 to block 3, and view the Special space of block 3:

Testdb=# select * from bt_page_stats ('pk_t_index',3) Blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags-+ -+-3 | r | 3 | 0 | 13 | 8192 | 8096 | 0 | 0 | 1 | 2 (1 row)

Type=r, which stands for root index block, this block has three index entries (live_items=3), and the index block is just root block (btpo_flags=BTP_ROOT). Let's take a look at the index entries in this block:

Testdb=# select * from bt_page_items ('pk_t_index',3) Itemoffset | ctid | itemlen | nulls | vars | data-+-1 | (1) | 8 | f | f | 2 | (2jing53) | 16 | f | f | 7b 01 00 00 00 3 | (4105) | 16 | f | f | e9 02 00 00 00 (3 rows)

Root/branch index block stores pointers to other index block. In line 1, index entries points to the first index block, and because the block has no left block, the itemlen is only 8 bytes, with a data range of 1 -\ x0000017b (decimal values of 379b); line 2, index entries points to the second index block, with a data range of 380 -\ x000002e9 (745); and line 3, index entries points to the fourth index block, with a data range greater than 745s.

There is a puzzle here. Normally, the entries in root index block should point to index block, but the values of ctid (2 Magne53) and (4105) point to Heap Table Block,PG11 Beta2's Bug?

In a B-tree leaf page, ctid points to a heap tuple. In an internal page, the block number part of ctid points to another page in the index itself, while the offset part (the second number) is ignored and is usually 1.

Testdb=# select * from heap_page_items (get_raw_page ('tasking indexer Magazine 2)) where t_ctid =' (2Magne53)' Lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_bits | t_oid | t_data-+- -- +-53 | 5648 | 1 | 43 | 1612755 | 0 | (2 row 53) | 3 | 2306 | 24 |\ x7b0100001323333739232020200d2333373923 (1 row) testdb=# select * from heap_page_items (get_raw_page ('tweak index') 4) where t_ctid ='(4105)' Lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_bits | t_oid | t_data-+- -+-+ 3152 | 1 | 43 | 1612755 | 0 | 726 | (4105) | 3 | 2306 | 24 |\ xe90200001323373435232020200d2337343523 (1 row)

Back to the point, let's first take a look at the data related to index block 1:

Testdb=# select * from bt_page_stats ('pk_t_index',1) Blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags-+ -+-1 | l | 367 | 0 | 16 | 8192 | 8192 | 0 | 2 | 0 | 1 (1 row) testdb=# select * from bt_page_items ('pk_t_index' 1) limit 10 Itemoffset | ctid | itemlen | nulls | vars | data-+-1 | (2meme 53) | 16 | f | f | 7b 01 00 00 00 00 00 2 | (0Jue 1) | 16 | f | f | 02 00 00 00 3 | (0Jue 2) | 16 | f | f | 04 00 00 00 4 | (0Jue 3) | 16 | f | f | 08 00 00 00 5 | (0P4) | 16 | f | f | 10 00 00 00 00 00 6 | (0prit 6) | 16 | f | f | 11 00 00 00 7 | (0prit 5) | 16 | f | f | 12 00 00 00 8 | (0prit 8) | 16 | f | f | 13 00 00 00 9 | (0prit 9) | 16 | f | f | 14 00 00 00 00 00 10 | (0jue 10) | 16 | f | f | 15 00 00 00 (10 rows)

The Special space of the first block, where type=l indicates that leaf index block,btpo_flags=BTP_LEAF indicates that the block only points to heap table for the index entries of leaf index block,block. At the same time, there are 367 items in this block, and the block number on the right is 2 (btpo_next).

It is worth noting that the first entry for index entries is the maximum value\ x017b, the second entry is the minimum value, and the next entry is the other values stored sequentially. The README (src/backend/access/nbtree/README) of the source code has an explanation:

On a page that is not rightmost in its tree level, the "high key" is

Kept in the page's first item, and real data items start at item 2.

The link portion of the "high key" item goes unused. A page that is

Rightmost has no "high key", so data items start with the first item.

Putting the high key at the left, rather than the right, may seem odd

But it avoids moving the high key as we add data items.

There are also explanations in the official documents:

Note that the first item on any non-rightmost page (any page with a non-zero value in the btpo_next field) is the page's "high key", meaning its data serves as an upper bound on all items appearing on the page, while its ctid field is meaningless. Also, on non-leaf pages, the first real data item (the first item that is not a high key) is a "minus infinity" item, with no actual value in its data field. Such an item does have a valid downlink in its ctid field, however.

Let's take a look at index block 2: 4:

Testdb=# select * from bt_page_stats ('pk_t_index',2) Blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags-+ -+-2 | l | 367 | 0 | 16 | 8192 | 8192 | 1 | 4 | 0 | 1 (1 row) testdb=# select * from bt_page_items ('pk_t_index' 2) limit 10 Itemoffset | ctid | itemlen | nulls | vars | data-+-1 | (4105) | 16 | f | f | e9 02 00 00 00 00 2 | (2Power53) | 16 | f | f | 7b 01 00 00 00 3 | (2Mague 54) | 16 | f | f | 7c 01 00 00 00 4 | (2jue 55) | 16 | f | f | 7d 01 00 00 00 5 | (2Mague 56) | 16 | f | f | 7e 01 00 | 00 00 00 6 | (2Power57) | 16 | f | f | 7f 01 00 00 00 7 | (2Mague 58) | 16 | f | f | 8001 00 00 00 8 | (2Mague 59) | 16 | f | f | 81 01 00 00 00 9 | (2Mague 60) | 16 | f | f | 82 01 00 00 00 00 10 | (2 rows 61) | 16 | f | f | 83 01 00 00 00 (10 rows) testdb=# select * from bt_page_stats ('pk_t_index') 4) Blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags-+ -+-4 | l | 276 | 0 | 16 | 8192 | 2628 | 2 | 0 | 1 (1 row) testdb=# select * from bt_page_items ('pk_t_index') 4) limit 10 Itemoffset | ctid | itemlen | nulls | vars | data-+-1 | (4105) | 16 | f | f | e9 02 00 00 00 00 2 | (4106) | 16 | f | f | ea 02 00 00 00 3 | (4107) | 16 | f | f | eb 02 00 00 00 4 | (4108) | 16 | f | f | ec 02 00 00 00 5 | (4109) | 16 | f | f | ed 02 00 00 00 6 | (4110) | 16 | f | f | ee 02 00 00 00 7 | (4111) | 16 | f | f | ef 02 00 00 00 8 | (4112) | 16 | f | f | f0 02 00 00 00 9 | (4113) | 16 | f | f | F1 02 00 00 00 10 | (4114) | 16 | f | f | f2 02 00 00 00 (10 rows) Thank you for your reading The above is the content of "what is the physical storage structure of PostgreSQL database B-Tree index". After the study of this article, I believe you have a deeper understanding of the physical storage structure of PostgreSQL database B-Tree index, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.