{"id":39,"date":"2020-10-04T17:23:25","date_gmt":"2020-10-04T17:23:25","guid":{"rendered":"https:\/\/maboc.nl\/?p=39"},"modified":"2020-10-04T17:23:25","modified_gmt":"2020-10-04T17:23:25","slug":"btree-balanced-tree-index","status":"publish","type":"post","link":"https:\/\/maboc.nl\/?p=39","title":{"rendered":"Btree : Balanced tree index"},"content":{"rendered":"\n<p>Let&#8217;s draw a table (any table). For simplicity I say:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>a block can only cater for 4 rows<\/li><li>The table has 2 columns (ID and Text)<\/li><li>Oracle assigns a rownumber within the block for every row<\/li><\/ul>\n\n\n\n<p><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>+--------------------+\n|Block_ID : 78       |\n+------+-------------+\n|rownum|  ID |  Text |\n+------+-----+-------+\n| 01   | 152 | AAAAA |\n| 02   | 153 | AAAAB |\n| 03   | 154 | AAAAC |\n| 04   | 152 | AAAAD |\n+------+-----+-------+\n+--------------------+\n|Block_ID : 79       |\n+------+-------------+\n|rownum|  ID |  Text |\n+------+-----+-------+\n| 01   | 153 | AAAAE |\n| 02   | 154 | AAAAF |\n| 03   | 155 | AAABA |\n| 04   | 166 | AAABB |\n+------+-----+-------+\n+--------------------+\n|Block_ID : 80       |\n+------+-------------+\n|rownum|  ID |  Text |\n+------+-----+-------+\n| 01   | 167 | AAABC |\n| 02   | 165 | AAABD |\n| 03   | 152 | AAABE |\n| 04   | 153 | AAABF |\n+------+-----+-------+\n+--------------------+\n|Block_ID : 81       |\n+------+-------------+\n|rownum|  ID |  Text |\n+------+-----+-------+\n| 01   | 153 | AAAAE |\n| 02   | 154 | AAAAF |\n| 03   | 155 | AAABA |\n| 04   | 180 | AAABB |\n+------+-----+-------+\n+--------------------+\n|Block_ID : 82       |\n+------+-------------+\n|rownum|  ID |  Text |\n+------+-----+-------+\n| 01   | 167 | AAABC |\n| 02   | 165 | AAABD |\n| 03   | 152 | AAABE |\n| 04   | 153 | AAABF |\n+------+-----+-------+<\/code><\/pre>\n\n\n\n<p>If I would like to see all rows where ID=154, Oracle would have to look in all blocks, and returns following rows <\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Block 78 Rownum 03<\/li><li>Block 79 Rownum 02<\/li><li>Block 81 Rownum 02<\/li><\/ul>\n\n\n\n<p>Oracle has to scan all 5 blocks (Full Table Scan) to get 3 rows. You could say Oracle did not need to scan block 80 and 82, because there is no ID=154 in those blocks. But how can oracle know that? It doesn&#8217;t without actually reading the block.<\/p>\n\n\n\n<p>Now indexes come into play. An index is essentially an ordered list of values found in a column (or multiple columns) coupled with a pointer to where to find that row.  Let&#8217;s see whether I can draw that.<\/p>\n\n\n\n<p>Assumptions (for simplicity):<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>We are creating an index on column ID<\/li><li>An index block can contain 6 rows<\/li><li>Oracle adds a pointer to the previous and the next block.<\/li><\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>+------------------+\n|(Leaf) Block : 67 |\n+------------------+\n| Prev: NULL       |\n+------------------+ \n| Next: 68         |\n+-----+-----+------+\n|Value|Block|Rownum|\n+-----+-----+------+\n|  152|   78|    01|\n|  152|   78|    04|\n|  152|   80|    03|\n|  152|   82|    03|\n|  153|   78|    02|\n|  153|   79|    01|\n+-----+-----+------+\n+------------------+\n|(Leaf) Block : 68 |\n+------------------+\n| Prev: 67         |\n+------------------+ \n| Next: 69         |\n+-----+-----+------+\n|Value|Block|Rownum|\n+-----+-----+------+\n|  153|   80|    04|\n|  153|   81|    01|\n|  153|   82|    04|\n|  154|   78|    03|\n|  154|   79|    02|\n|  154|   81|    02|\n+-----+-----+------+\n+------------------+\n|(Leaf) Block : 69 |\n+------------------+\n| Prev: 68         |\n+------------------+ \n| Next: 70         |\n+-----+-----+------+\n|Value|Block|Rownum|\n+-----+-----+------+\n|  155    79|    03|\n|  155|   81|    03|\n|  165|   80|    02|\n|  165|   82|    02|\n|  166|   79|    04|\n+-----+-----+------+\n+------------------+\n|(Leaf) Block : 70 |\n+------------------+\n| Prev: 69         |\n+------------------+ \n| Next: NULL       |\n+-----+-----+------+\n|Value|Block|Rownum|\n+-----+-----+------+\n|  167|   89|    01|\n|  167|   82|    01|\n|  180|   81|    04|\n|  ...|   ..|    ..|\n|  ...|   ..|    ..|\n|  ...|   ..|    ..|\n+-----+-----+------+<\/code><\/pre>\n\n\n\n<p>This is nice for a start. Specially, when I\u00b4m looking for a value in the first block of the index.  Let&#8217;s say I&#8217;m now looking for all rows with ID=152. I start reading the first block of the index and found the value I&#8217;m looking for. I find four pointers to rows where ID=152. <\/p>\n\n\n\n<ul class=\"wp-block-list\"><li> Block 78 Rownumber 01<\/li><li>Block 78 Rownumber 04<\/li><li>Block 80 Rownumber 03<\/li><li>Block 82 Rownumber 03<\/li><\/ul>\n\n\n\n<p>So to get the rows I need to visit block 78, 80 and 82. In total I visited 1 index block and 3 table blocks. That is 4 blocks. That is allready a bit better, then searching through the 5 blocks of the table.<\/p>\n\n\n\n<p>But&#8230;.Now it like to find the rows where ID=165 .<\/p>\n\n\n\n<p>I start reading the first index block, second block, and then find 165 at the third block. Finally I have to visit the 2 data blocks Block 80 Rownumber 02 and Block 82 Rownumber 02. Luckiky Oracle added forward pointers to the next index block, so we do not have to search for a block, because we have the pointer we just know the next block.<\/p>\n\n\n\n<p>Now I have a total of 3 index blocks plus 2 data blocks, which makes 5 blocks. That is just as expensive as reading through the whole table \ud83d\ude41<\/p>\n\n\n\n<p>So we&#8217;re not there yet. Now the magic of the balanced tree comes to play:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>+------------------+  +------------------+\n|(Leaf) Block : 67 |  |(Branch) Block: 51|\n+------------------+  +------+----+------+\n| Prev: Nul        |  |Start | End| Block| \n+------------------+  +------+----+------+\n| Next: 68         |  |   152| 153|    67|\n+-----+-----+------+  |   153| 154|    68|\n|Value|Block|Rownum|  |   155| 156|    69|\n+-----+-----+------+  |   167| 180|    70| \n|  152|   78|    01|  |   ...| ...|   ...|\n|  152|   78|    04|  |   ...| ...|   ...|\n|  152|   80|    03|  +------+----+------+\n|  152|   82|    03|  \n|  153|   78|    02|  \n|  153|   79|    01|  \n+-----+-----+------+  \n+------------------+\n|(Leaf) Block : 68 |\n+------------------+\n| Prev: 67         |\n+------------------+ \n| Next: 69         |\n+-----+-----+------+\n|Value|Block|Rownum|\n+-----+-----+------+\n|  153|   80|    04|\n|  153|   81|    01|\n|  153|   82|    04|\n|  154|   78|    03|\n|  154|   79|    02|\n|  154|   81|    02|\n+-----+-----+------+\n+------------------+\n|(Leaf) Block : 69 |\n+------------------+\n| Prev: 68         |\n+------------------+ \n| Next: 70         |\n+-----+-----+------+\n|Value|Block|Rownum|\n+-----+-----+------+\n|  155    79|    03|\n|  155|   81|    03|\n|  165|   80|    02|\n|  165|   82|    02|\n|  166|   79|    04|\n+-----+-----+------+\n+------------------+\n|(Leaf) Block : 70 |\n+------------------+\n| Prev: 69         |\n+------------------+ \n| Next: NULL       |\n+-----+-----+------+\n|Value|Block|Rownum|\n+-----+-----+------+\n|  167|   89|    01|\n|  167|   82|    01|\n|  180|   81|    04|\n|  ...|   ..|    ..|\n|  ...|   ..|    ..|\n|  ...|   ..|    ..|\n+-----+-----+------+<\/code><\/pre>\n\n\n\n<p>An extra level in the index is added.  This is a branch block (and also the root block). In an index we have two types of blocks:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li> Leaf blocks (which points actually to rows of data)<\/li><li>Branch blocks (which points to other index blocks)<\/li><li>(and maybe a root block, which is the very first branch block)<\/li><\/ol>\n\n\n\n<p>So let&#8217;s say I&#8217;d like to look up all rows where ID=167, then I start reading at the index root block. This tells me that I can find values from 167 to 180 at index leaf block 70. Now I look up index leaf block 70, which show me that value 167 can be found in data block 89 rownumner 01 and data block 82 rownumber 01.<\/p>\n\n\n\n<p>In total 4 blocks read. You might think that is not a real improvement, but thin of it:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For every value of ID you search for you only have to read 2 blocks of index-data (in this case), and then (ofcourse) the data blocks. It doen matter if you want he last or the first value, searching is always the same depth.<\/li><li>The above is just a example, in reality 100&#8217;s of entrys fir in an index block, so in reality the above index would consist of 1 block.  <\/li><\/ul>\n\n\n\n<p>In a following writing I will describe:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>adding a few values to this table (and consequently to the index)<\/li><li>index block splits<\/li><li>when will an index be used (Help, my index isn&#8217;t used)<\/li><\/ol>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Let&#8217;s draw a table (any table). For simplicity I say: a block can only cater for 4 rows The table has 2 columns (ID and Text) Oracle assigns a rownumber within the block for every row If I would like to see all rows where ID=154, Oracle would have to look in all blocks, and [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[9,8],"class_list":["post-39","post","type-post","status-publish","format-standard","hentry","category-oracle","tag-btree","tag-index"],"_links":{"self":[{"href":"https:\/\/maboc.nl\/index.php?rest_route=\/wp\/v2\/posts\/39","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/maboc.nl\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/maboc.nl\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/maboc.nl\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/maboc.nl\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=39"}],"version-history":[{"count":17,"href":"https:\/\/maboc.nl\/index.php?rest_route=\/wp\/v2\/posts\/39\/revisions"}],"predecessor-version":[{"id":64,"href":"https:\/\/maboc.nl\/index.php?rest_route=\/wp\/v2\/posts\/39\/revisions\/64"}],"wp:attachment":[{"href":"https:\/\/maboc.nl\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=39"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/maboc.nl\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=39"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/maboc.nl\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=39"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}