Why B-tree indexing is used instead of hash based indexing? [duplicate]

Question

I have an employee table which has index on name. I want to understand how Oracle works at high level

My understanding based on resources mentioned below:-

DB constructs the index table/map where it will keep the name in sorted fashion with memory location as the value.

Question :-

1. My question is will oracle bring all index table/map entries in memory from disc and then do the binary search or is it the search at disc level without bringing all index table records in memory?

2. If I compare this approach with Java based data structures, Oracle is maintaining the TreeMap of column where key is employee name and value is memory location of that entry. So to find any entry, look up time will be log(n). My question why not DB/oracle takes hash based approach where it keeps the hashtable where it calculate the memory location based on name value and put the entry there. So lookup time to find entry will be O(1) .

Resources I referred

1. "Indexes and Index-Organized Tables" from the Oracle manual

2. How does database indexing work

Answer 1

Oracle will not read all the index; only the index blocks needed to satisfy the particular query. The number of blocks will depend on the depth of the index; rarely more than three have I seen in practice, for a single lookup.

Here is an example, using a big version of the EMP table. BIGEMP contains just under 2M rows:

select count(*) from bigemp
;

  COUNT(*)
----------
   1835008

I have created a unique index, called IDX1 on empno. Now I can examine the BLEVEL (which is what I was referring to as depth above) and the number of leaf blocks:

 select index_name, blevel, leaf_blocks
 from user_indexes
 where index_name = 'IDX1'
 ;

INDEX_NAME               BLEVEL LEAF_BLOCKS
-------------------- ---------- -----------
IDX1                          2        3947

So this tells me that this index has a root node, and then two level below that. So this mean that to find a unique row from the table, it should only take 4 IO's. That is the index root block, the two leaf blocks, and then another IO to the table to get the actual rows. This can be verified using autotrace

SQL> set autotrace on
SQL> select empno, ename, sal
  2  from bigemp
  3  where empno = 12345
  4  /

     EMPNO ENAME             SAL
---------- ---------- ----------
     12345 Scott            3000


Execution Plan
----------------------------------------------------------
Plan hash value: 3460625844

--------------------------------------------------------------------------------------
| Id  | Operation                   | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |        |     1 |    15 |     3   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| BIGEMP |     1 |    15 |     3   (0)| 00:00:01 |
|*  2 |   INDEX UNIQUE SCAN         | IDX1   |     1 |       |     2   (0)| 00:00:01 |
--------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("EMPNO"=12345)


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
          4  consistent gets
          1  physical reads
          0  redo size
        682  bytes sent via SQL*Net to client
        551  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

Sure enough, 4 consistent gets.

Oracle does also support "hash indexing" - called hash clusters. However, for transactional systems, there is a big maintenance penalty on them, so they are rarely used in these systems.