数据库索引的运行原理及基本结构

索引：是一种独立、物理的存储数据表一列或多列数值的一个有序的数据结构。（聚簇索引，是物理顺序和键值顺序一致，所以是一张表只能建立一个聚簇索引；非聚簇索引则反之。）同时包涵索引数据，还有指向列数据的数据表的指针表单
索引建立目的主要是提高数据的检索速度，当检索时，通过索引找到相应的键值，然后根据键值的指针找到对应的行，完成检索。
简单的说，索引就像是书的目录，通过查找页码，找到想要阅读的信息。

主要索引：唯一索引、主键索引和聚集索引。

在数据库系统中建立索引主要有以下作用：
（1）快速取数据；
（2）保证数据记录的唯一性；（唯一索引，插入数据时会比较是否有相同的键值）
（3）实现表与表之间的参照完整性；
（4）在使用ORDER by、group by子句进行数据检索时，利用索引可以减少排序和分组的时间。（键值指针顺序已经完成分组）

优点
1.大大加快数据的检索速度;
2.创建唯一性索引，保证数据库表中每一行数据的唯一性;
3.加速表和表之间的连接;
4.在使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间。
缺点
1.索引需要占物理空间。
2.当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，降低了数据的维护速度。

索引的实现是基于B树及它的变种树；那么为什么是基于B树呢？

局部性原理：当一个数被操作时，那么它附近的数也将被操作，程序运行期间所需要的数据通常比较集中。

磁盘预读原理：磁盘I/O操作时，会通过预读，提高IO效率。预读一般是页的倍数，页是计算机为了管理存储器将其分的块单元。

由于局部性原理和磁盘预读的特性，在建立B树节点时，可以申请一页的空间，这样在操作节点时，空间和计算机的IO大小是一致的，减少了不必要的IO操作。

为什么不用红黑树呢？

红黑树，是平衡二叉树，其节点物理结构中距离跟节点过远，预读效果没有B树明显。

上图展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。

B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

附：
1）B树

B树中每个节点包含了键值和键值对于的数据对象存放地址指针，所以成功搜索一个对象可以不用到达树的叶节点。

成功搜索包括节点内搜索和沿某一路径的搜索，成功搜索时间取决于关键码所在的层次以及节点内关键码的数量。

在B树中查找给定关键字的方法是：首先把根结点取来，在根结点所包含的关键字K1,…,kj查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查的关键字在某个Ki或Ki+1之间，于是取Pi所指的下一层索引节点块继续查找，直到找到，或指针Pi为空时查找失败。

2）B+树

B+树非叶节点中存放的关键码并不指示数据对象的地址指针，非也节点只是索引部分。所有的叶节点在同一层上，包含了全部关键码和相应数据对象的存放地址指针，且叶节点按关键码从小到大顺序链接。如果实际数据对象按加入的顺序存储而不是按关键码次数存储的话，叶节点的索引必须是稠密索引，若实际数据存储按关键码次序存放的话，叶节点索引时稀疏索引。

B+树有2个头指针，一个是树的根节点，一个是最小关键码的叶节点。

所以 B+树有两种搜索方法：

一种是按叶节点自己拉起的链表顺序搜索。

一种是从根节点开始搜索，和B树类似，不过如果非叶节点的关键码等于给定值，搜索并不停止，而是继续沿右指针，一直查到叶节点上的关键码。所以无论搜索是否成功，都将走完树的所有层。

B+ 树中，数据对象的插入和删除仅在叶节点上进行。

这两种处理索引的数据结构的不同之处：
a，B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡。
b，因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
c，B树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。

部分借鉴：
http://blog.****.net/kennyrose/article/details/7532032；
http://www.oschina.net/question/565065_86338
相互学习，共同成长，谢谢