一、索引的原理

说白了，索引问题就是一个查找问题。数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用b树及其变种b+树。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
为表设置索引要付出代价的：一是增加了数据库的存储空间，二是在插入和修改数据时要花费较多的时间(因为索引也要随之变动)。

上图展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在o(logd⁡(n/2)“>logd(n/2)logd⁡(n/2)，检索一个key，其查找节点个数的渐进复杂度为o(logd⁡n“>logdnlogd⁡n)，所以树的出度d越大，深度h就越小，i/o的次数就越少。b+tree恰恰可以增加出度d的宽度，因为每个节点大小为一个页大小，所以出度的上限取决于节点内key和data的大小：
dmax=floor(pagesize/(keysize+datasize+pointsize))//floor表示向下取整
由于b+tree内节点去掉了data域，因此可以拥有更大的出度，从而拥有更好的性能。

b+树查找过程

b-树和b+树查找过程基本一致。如上图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次io，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的p2指针，内存时间因为非常短（相比磁盘的io）可以忽略不计，通过磁盘块1的p2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次io，29在26和30之间，锁定磁盘块3的p2指针，通过指针加载磁盘块8到内存，发生第三次io，同时内存中做二分查找找到29，结束查询，总计三次io。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次io，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次io，那么总共需要百万次的io，显然成本非常非常高。

转自：https://www.cnblogs.com/kungfupanda/p/12873942.html

需要了解更多数据库技术:索引原理及B树索引，都可以关注数据库技术分享栏目—计算机技术网(www.ctvol.com)!