Let’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
+--------------------+
|Block_ID : 78 |
+------+-------------+
|rownum| ID | Text |
+------+-----+-------+
| 01 | 152 | AAAAA |
| 02 | 153 | AAAAB |
| 03 | 154 | AAAAC |
| 04 | 152 | AAAAD |
+------+-----+-------+
+--------------------+
|Block_ID : 79 |
+------+-------------+
|rownum| ID | Text |
+------+-----+-------+
| 01 | 153 | AAAAE |
| 02 | 154 | AAAAF |
| 03 | 155 | AAABA |
| 04 | 166 | AAABB |
+------+-----+-------+
+--------------------+
|Block_ID : 80 |
+------+-------------+
|rownum| ID | Text |
+------+-----+-------+
| 01 | 167 | AAABC |
| 02 | 165 | AAABD |
| 03 | 152 | AAABE |
| 04 | 153 | AAABF |
+------+-----+-------+
+--------------------+
|Block_ID : 81 |
+------+-------------+
|rownum| ID | Text |
+------+-----+-------+
| 01 | 153 | AAAAE |
| 02 | 154 | AAAAF |
| 03 | 155 | AAABA |
| 04 | 180 | AAABB |
+------+-----+-------+
+--------------------+
|Block_ID : 82 |
+------+-------------+
|rownum| ID | Text |
+------+-----+-------+
| 01 | 167 | AAABC |
| 02 | 165 | AAABD |
| 03 | 152 | AAABE |
| 04 | 153 | AAABF |
+------+-----+-------+If I would like to see all rows where ID=154, Oracle would have to look in all blocks, and returns following rows
- Block 78 Rownum 03
- Block 79 Rownum 02
- Block 81 Rownum 02
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’t without actually reading the block.
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’s see whether I can draw that.
Assumptions (for simplicity):
- We are creating an index on column ID
- An index block can contain 6 rows
- Oracle adds a pointer to the previous and the next block.
+------------------+
|(Leaf) Block : 67 |
+------------------+
| Prev: NULL |
+------------------+
| Next: 68 |
+-----+-----+------+
|Value|Block|Rownum|
+-----+-----+------+
| 152| 78| 01|
| 152| 78| 04|
| 152| 80| 03|
| 152| 82| 03|
| 153| 78| 02|
| 153| 79| 01|
+-----+-----+------+
+------------------+
|(Leaf) Block : 68 |
+------------------+
| Prev: 67 |
+------------------+
| Next: 69 |
+-----+-----+------+
|Value|Block|Rownum|
+-----+-----+------+
| 153| 80| 04|
| 153| 81| 01|
| 153| 82| 04|
| 154| 78| 03|
| 154| 79| 02|
| 154| 81| 02|
+-----+-----+------+
+------------------+
|(Leaf) Block : 69 |
+------------------+
| Prev: 68 |
+------------------+
| Next: 70 |
+-----+-----+------+
|Value|Block|Rownum|
+-----+-----+------+
| 155 79| 03|
| 155| 81| 03|
| 165| 80| 02|
| 165| 82| 02|
| 166| 79| 04|
+-----+-----+------+
+------------------+
|(Leaf) Block : 70 |
+------------------+
| Prev: 69 |
+------------------+
| Next: NULL |
+-----+-----+------+
|Value|Block|Rownum|
+-----+-----+------+
| 167| 89| 01|
| 167| 82| 01|
| 180| 81| 04|
| ...| ..| ..|
| ...| ..| ..|
| ...| ..| ..|
+-----+-----+------+This is nice for a start. Specially, when I´m looking for a value in the first block of the index. Let’s say I’m now looking for all rows with ID=152. I start reading the first block of the index and found the value I’m looking for. I find four pointers to rows where ID=152.
- Block 78 Rownumber 01
- Block 78 Rownumber 04
- Block 80 Rownumber 03
- Block 82 Rownumber 03
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.
But….Now it like to find the rows where ID=165 .
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.
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 🙁
So we’re not there yet. Now the magic of the balanced tree comes to play:
+------------------+ +------------------+
|(Leaf) Block : 67 | |(Branch) Block: 51|
+------------------+ +------+----+------+
| Prev: Nul | |Start | End| Block|
+------------------+ +------+----+------+
| Next: 68 | | 152| 153| 67|
+-----+-----+------+ | 153| 154| 68|
|Value|Block|Rownum| | 155| 156| 69|
+-----+-----+------+ | 167| 180| 70|
| 152| 78| 01| | ...| ...| ...|
| 152| 78| 04| | ...| ...| ...|
| 152| 80| 03| +------+----+------+
| 152| 82| 03|
| 153| 78| 02|
| 153| 79| 01|
+-----+-----+------+
+------------------+
|(Leaf) Block : 68 |
+------------------+
| Prev: 67 |
+------------------+
| Next: 69 |
+-----+-----+------+
|Value|Block|Rownum|
+-----+-----+------+
| 153| 80| 04|
| 153| 81| 01|
| 153| 82| 04|
| 154| 78| 03|
| 154| 79| 02|
| 154| 81| 02|
+-----+-----+------+
+------------------+
|(Leaf) Block : 69 |
+------------------+
| Prev: 68 |
+------------------+
| Next: 70 |
+-----+-----+------+
|Value|Block|Rownum|
+-----+-----+------+
| 155 79| 03|
| 155| 81| 03|
| 165| 80| 02|
| 165| 82| 02|
| 166| 79| 04|
+-----+-----+------+
+------------------+
|(Leaf) Block : 70 |
+------------------+
| Prev: 69 |
+------------------+
| Next: NULL |
+-----+-----+------+
|Value|Block|Rownum|
+-----+-----+------+
| 167| 89| 01|
| 167| 82| 01|
| 180| 81| 04|
| ...| ..| ..|
| ...| ..| ..|
| ...| ..| ..|
+-----+-----+------+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:
- Leaf blocks (which points actually to rows of data)
- Branch blocks (which points to other index blocks)
- (and maybe a root block, which is the very first branch block)
So let’s say I’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.
In total 4 blocks read. You might think that is not a real improvement, but thin of it:
- 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.
- The above is just a example, in reality 100’s of entrys fir in an index block, so in reality the above index would consist of 1 block.
In a following writing I will describe:
- adding a few values to this table (and consequently to the index)
- index block splits
- when will an index be used (Help, my index isn’t used)