数据库中的索引，原理是什么？为什么查询使用索引就会快？

这个问题和线性查询、二分查询是有很大关系的。索引后的数据可以使用二分法查询，未索引的数据查询需要线性查询。下面详细说一下这两者之间的性能区别。

1、两者的查询原理

①、线性查询

线性查询又称顺序查询，它的查询原理就是从第一条记录开始，逐个比较要查找的字段，直到字段内容和查找值相等，则查找成功，返回结果。若比较结果与字段所有记录都不等，则查找失败。下面举例说明：

需要在某个记录数为N的数组a[]中查找元素k，那么，线性查询就是从a[1]开始和k进行对比，对比相等则返回a[i]，如果，不相等则继续下一个查询， i=i+1。直到 i=N为止。那线性查询的性能就一目了然：

• 最好的情况就是对比1次就找到结果。
• 最差的情况就是需要对比N次才能找到结果。
• 平均计算，就是N/2次能找到结果。

②、二分查询

二分法查询也可以说是分段查询。主要原理就是对已经排序的一组数据进行中间分段，中间分界点和查询值对比。如果数值小于分界点，则要查找的数落在前半段；如果数字大于分界点，则要查找的数落在前半段；如果等于分界点，则要查找数就已经找到。下面同样举例说明：

需要在某个记录数为N且已经排好序的数组a[]中查找元素K，那么，二分查询首先是确定数组的中点a[x]，其实也就是a[N/2]这个值（N/2采用进一法取整）。然后对比a[x]和K值，按照前面的方法循环缩小对比的区间，最终找到想要的值。二分查询的性能如下：

• 二分法查询N条记录需要log2（N）次对比就能找到结果。
• 前提是：数组必须要排好序

★从上面两种查询法原理可以看到，当数组N比较大时，二分查询的查询性能明显优于线性查询。当数组N较小时，则线性查询的性能更好，因为它少了求中值的开销。

2、索引给数据库查询带来的性能变化

数据库中建立索引其实就是对数据库表中一列或多列的值进行排序的结构。其实就是为了给二分查询做好排序的前提。结合前面两种查询的原理，我们就很容易理解数据库中索引变快的原因了。其实，数据库通常情况下，数据量都是比较大的，一般都是上万条，甚至达到亿级记录。我们用前面原理中的公式计算对比一下：

• 在10万条记录中查找一个值：那么，N=100000；
• 线性查询性能=N/2，计算可得，平均需要对比50000次;
• 二分查询性能=log2(N)，计算可得，大约需要17次；

从上面计算对比，我们可以看到，索引好了用二分查询的性能会比线性查询快非常多。

3、数据库哪里应该加索引

虽然加了索引后，查询性能提升很多。但是在数据库里面也是不所有字段都加索引的，因为，数据库的整体性能不仅需要考虑查询性能，还需要考虑写入性能。当你在数据库中某个字段加入索引后，该字段就需要建立对应的索引指针。每次新写入或者修改字段的记录，都需要额外写入索引指针。所以，在数据库中，加入索引会加快搜索性能，但也会相应降低一点点写入性能。所以，数据库中建立索引一般在以下几种情况建立索引。

• 经常需要搜索的列，增加索引可以加快搜索速度；
• 作为主键的列，强制该列的唯一性和组织表中数据的排列结构；
• 在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度；
• 在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的
• 在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间
• 在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度

总结

总之，数据库中因为存在大量的数据，建立索引相当于对数据进行了排序，可以使用二分查询法来查询数据，确实会大大提高查询的速度。但是也会相应降低一点点写入的速度，所以，数据库中的索引也是有针对性的建立索引的。