Oracle Database - (B|Balanced) Tree - BTree indexes

Height Balanced Structure

To get to the leaf block to retrieve the first row of a query of the form

 SELECT INDEXED-COL FROM T WHERE INDEX_COL = :X

will take the same number of I/Os regardless of the value :X that is used. In other words, the index is height balanced

Most of B*Tree indexes will have a height of 2 or 3 even for millions of record. This means that it will take in general, two or three I/Os to find your key in the index which is not too bad.

Example

nico@ORCL>select index_name,blevel, num_rows
  2  from user_indexes
  3  where table_name = 'BIG_TABLE';

INDEX_NAME                         BLEVEL   NUM_ROWS
------------------------------ ---------- ----------
BIG_TABLE_PK                            2    9542757

nico@ORCL>set autotrace on;
nico@ORCL>select id from big_table where id = 42;

----------------------------------------------------------------------------------
| Id  | Operation         | Name         | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |              |     1 |     6 |     2   (0)| 00:00:01 |
|*  1 |  INDEX UNIQUE SCAN| BIG_TABLE_PK |     1 |     6 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------------

Statistics
----------------------------------------------------------
          3  consistent gets
          1  rows processed

nico@ORCL>select id from big_table where id = 5000000;

Execution Plan
----------------------------------------------------------------------------------
| Id  | Operation         | Name         | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |              |     1 |     6 |     2   (0)| 00:00:01 |
|*  1 |  INDEX UNIQUE SCAN| BIG_TABLE_PK |     1 |     6 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------------

Statistics
----------------------------------------------------------
          3  consistent gets
          1  rows processed

Whenever the value selected 42 of 5000000, you will have always the same statistics :

• 3 consistent gets (three I/Os)
• 1 rows processed

Concept

The basic concept behind a compressed key index is that every entry is broken into two pieces :

• a prefix component . It's build on the leading columns of the concatenated index and will have many repeating values.
• and a suffix component. It's built on the trailing columns in the index key and is the unique component of the index entry within the prefix.

Index block with owner colomn repeated

Sys.Package.Dbms_Alert
Sys.Package.Dbms_Application_info
Sys.Package.Dbms_Aq
Sys.Package.Dbms_Aqadm
Sys.Package.Dbms_Aqadm_Sys
Sys.Package.Dbms_Alert_Syscalls
...

become

Index block with owner colomn factored out

**Sys** //<- prefix//
Package.Dbms_Alert //<- suffix ...//
Package.Dbms_Application_info
Package.Dbms_Aq
Package.Dbms_Aqadm
Package.Dbms_Aqadm_Sys
Package.Dbms_Alert_Syscalls
...

Example

nico@ORCL>create table t
  2  as
  3  select * from all_objects;

Table created.

nico@ORCL>create index t_idx on t(owner, object_type, object_name);

Index created.

nico@ORCL>analyze index t_idx validate structure;

Index analyzed.

nico@ORCL>create table idx_stats
  2  as
  3  select 'noncompressed' what, a.*
  4  from index_stats a;

Table created.

nico@ORCL>define 1=1;
nico@ORCL>drop index t_idx;

Index dropped.

nico@ORCL>create index t_idx on t(owner,object_type,object_name) compress &1;
old   1: create index t_idx on t(owner,object_type,object_name) compress &1
new   1: create index t_idx on t(owner,object_type,object_name) compress 1

Index created.

nico@ORCL>analyze index t_idx validate structure;

Index analyzed.

nico@ORCL>insert into idx_stats select 'compress &1', a.* from index_stats a;
old   1: insert into idx_stats select 'compress &1', a.* from index_stats a
new   1: insert into idx_stats select 'compress 1', a.* from index_stats a

1 row created.

........................................
For compress 2 and 3 same procedure ....
........................................

nico@ORCL>select what, height, lf_blks, br_blks, btree_space, opt_cmpr_count, opt_cmpr_pctsave
  2  from idx_stats;

WHAT              HEIGHT    LF_BLKS    BR_BLKS BTREE_SPACE OPT_CMPR_COUNT OPT_CMPR_PCTSAVE
------------- ---------- ---------- ---------- ----------- -------------- ----------------
noncompressed          3        407          3     3280096              2               29
compress 1             3        354          3     2854680              2               19
compress 2             3        287          3     2318948              2                0
compress 3             3        455          3     3662276              2               36

• LF_BLKS = Leaf Blocks
• BR_BLKS = Branch Blocks
• OPT_CMPR_PCTSAV = Optimum compression percent saved (or the expected saving from compression)
• OPT_CMPR_COUNT = Optimum compression factor

We see for COMPRESS 1 :

• Comparing BTREE_SPACE, that the index is about 89 percent the size of the noncompressed index.
• the number of leaf blocks has decreased measurably

Further, we see for COMPRESS 2 :

• the saving are even more impressive. The resulting index is about 70 percent the size of the original, and so much data is able to be placed on individual blocks

nico@ORCL>select  3280096*(1-0.29) from dual;

3280096*(1-0.29)
----------------
      2328868.16

What happen for COMPRESS 3 :

• The resulting index is actually larger: 110 percent the size of the original index.

This is due to the fact that each repeated prefix we remove saves the space of N copies, but add 4 bytes of overhead on the leaf block as part of the compression scheme. By adding the OBJECT_NAME column to the compressed key, we made that key unique, meaning there were no duplicate copies to factor out. Therefore, we ended up adding 4 bytes to every single index key entry and factoring out no repeating data.

The column OPT_CMPR_COUNT is dead accurate at providing the best compression count to be used and OPT_CMPR_PCTSAVE will tell you exactly how much saving to expect.

Compression is not free

The compressed index structure is more complex than it used to be. Oracle will spend more time processing the data in this structure, both :

• while maintaining the index during modifications
• when you search the index during the query

What we search is the tradeoff between CPU time and I/O time.