(老问题)索引实现机制是什么？

Question

大家都知道有效的索引会提高查询速度，问题是通过什么提高速度的呢？查了很多就是找不到想要的答案

Answer 1

索引的根本目的是减少磁盘I/O
磁盘I/O速度是相当慢的。而索引的内容从根节点开始，很多级都可以在内存中访问。数据量大的数据本身就无法或很难做到这一点。

Answer 2

索引以二叉树的形式，按column key顺利存放，比如：
    70
60     80
     75   85
         83  86
查86的话只要按路径一直往右走来查，所以快了。

Answer 3

参考http://tech.it168.com/a2009/0603/582/000000582525.shtml
二、 索引的概念
　　1、 类似书的目录结构
　　2、 Oracle 的“索引”对象，与表关联的可选对象，提高SQL查询语句的速度
　　3、 索引直接指向包含所查询值的行的位置，减少磁盘I/O
　　4、 与所索引的表是相互独立的物理结构
　　5、 Oracle 自动使用并维护索引，插入、删除、更新表后，自动更新索引
　　6、 语法：CREATE INDEX index ON table (column[, column]...);
　　7、 B-tree结构(非bitmap)：
　　[一]了解索引的工作原理：
　　表：emp

Answer 4

数据库索引，最基本的看两个，一个B树，一个动态hash
其它的，看各个数据库的附加支持的特殊索引了。都有文档介绍。其实，好一点的数据库教材都有相关理论介绍。