主页 / dba / 问题 / 166170
Accepted
emilly
Asked: 2017-03-04 20:59:06 +0800 CST

为什么使用 B 树索引而不是基于散列的索引？[复制]

  • 772

我有一个员工表，其中包含名称索引。我想了解 Oracle 的高级工作原理

我基于以下资源的理解：-

DB 构建索引表/映射，它将在其中以内存位置作为值以排序的方式保存名称。

问题 ：-

  1. 我的问题是 oracle 会将所有索引表/映射条目从磁盘中放入内存中，然后进行二进制搜索，还是在磁盘级别搜索而不将所有索引表记录放入内存中？

  2. 如果我将这种方法与基于 Java 的数据结构进行比较，Oracle 正在维护列的 TreeMap，其中键是员工姓名，值是该条目的内存位置。所以要找到任何条目，查找时间将为 log(n)。我的问题是为什么 DB/oracle 不采用基于散列的方法，它将散列表保存在它根据名称值计算内存位置并将条目放在那里的位置。因此查找条目的查找时间为 O(1) 。

我提到的资源

  1. Oracle 手册中的“索引和索引组织表”

  2. 数据库索引是如何工作的

oracle index

1 个回答

  1. Best Answer

    Oracle不会读取所有的索引；只有满足特定查询所需的索引块。块的数量将取决于索引的深度；我在实践中很少看到超过三个，用于一次查找。

    下面是一个示例，使用了大版本的 EMP 表。BIGEMP 包含不到 2M 行：

    select count(*) from bigemp
;

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

    我在 empno 上创建了一个名为 IDX1 的唯一索引。现在我可以检查 BLEVEL（我在上面提到的深度）和叶块的数量：

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

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

    所以这告诉我这个索引有一个根节点，然后在它下面两层。所以这意味着要从表中找到一个唯一的行，它应该只需要 4 个 IO。那是索引根块，两个叶块，然后是对表的另一个 IO 以获取实际行。这可以使用 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

    果然，4个一致get。

    Oracle 还支持“散列索引”——称为散列簇。但是，对于事务系统，它们有很大的维护代价，因此很少在这些系统中使用它们。

    • 2

相关问题