和线性查询、二分查询是有很大关系的。索引后的数据可以使用二分法查询，未索引的数据查询需要线性查询。下面详细说一下这两者之间的性能区别。
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子句中的列上面创建索引，加快条件的判断速度
总结
总之，数据库中因为存在大量的数据，建立索引相当于对数据进行了排序，可以使用二分查询法来查询数据，确实会大大提高查询的速度。但是也会相应降低一点点写入的速度，所以，数据库中的索引也是有针对性的建立索引的。
以查字典为例，来说明。
先想象一下有一本字典，里面的字是随意排列的，我们要查一个字，就只能一页一页翻过去查找，这样下来查一个字就会花很多时间，如果运气不好，我们要找的字在最后一页，就得翻几千页了。用数据库的术语叫遍历（full scan）。
为了缩短查询时间，我们把字典里的字按照拼音字母的顺序排列好。这样查字的时候，查看一下中间那一页，就可以知道我们要查的字是在前面还是在后面。比如在前面，我们就查看1/4处的那一页，如此反复直到我们找到要查的字为止。那么这么做我们得查多少次呢？一本六万多页的字典最多查16次就能找到您想要的那一页了。这种方法要比遍历的方法快得多。用数据库的术语叫B-TREE(二叉树)。
如果我们不知道发音想按部首查字典又该怎么办呢？字典里按照部首的顺序做了个表，查这个表就可以快速查到解释那个字的页码了。这个表用数据库的术语就叫索引。
值得注意的是，索引是以字段为基础建立的，在检索的时候，如果对被索引的字段进行运算，就很可能打乱事前排好的顺序，导致不得不遍历数据，使索引失去效果。
原创文章，作者：普尔小编，如若转载，请注明出处：http://www.puerpx.cn/pxwd/9297.html
