数据库索引原理

MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。

二、常见的查询算法及数据结构

为什么这里要讲查询算法和数据结构呢？因为之所以要建立索引，其实就是为了构建一种数据结构，可以在上面应用一种高效的查询算法，最终提高数据的查询速度。

2.1 索引的本质

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。

2.2 常见的查询算法

我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。那么有哪些查询算法可以使查询速度变得更快呢？

2.2.1 顺序查找（linear search ）

最基本的查询算法当然是顺序查找（linear search），也就是对比每个元素的方法，不过这种算法在数据量很大时效率是极低的。
数据结构：有序或无序队列
复杂度：O(n)
实例代码：

/ /顺序查找
int SequenceSearch(int a[], int value, int n)
{
    int i;
for(i=0; i<n; i++)
    if(a[i]==value)
        return i;
return -1;
}

2.2.2 二分查找（binary search）

比顺序查找更快的查询方法应该就是二分查找了，二分查找的原理是查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
数据结构：有序数组
复杂度：O(logn)
实例代码：

  //二分查找，递归版本

  int BinarySearch2(int a[], int value, int low,               int high)
{
  int mid = low+(high-low)/2;
if(a[mid]==value)
    return mid;
if(a[mid]>value)
    return BinarySearch2(a, value, low, mid-1);
if(a[mid]<value)
    return BinarySearch2(a, value, mid+1, high);
}

----转载于[https://www.cnblogs.com/klb561/p/10666296.html]
----redis https://www.cnblogs.com/jasontec/p/9699242.html
(https://www.cnblogs.com/klb561/p/10666296.html)