本篇预备知识

当数据量大的时候，查询操作的效率变得非常重要。对于查询操作来说，如果被查询的数据已某种方式组织起来，那么查询操作的效率会极大提高。

在数据库中，一条记录会有很多列。如果把这些记录按照列Col1以某种数据结构组织起来，那么其他列可能是乱序的。因此，数据库在原始数据之外，维护了满足特定查找算法的数据结构，指向原始数据，称之为索引。

举例来说，在下面的图中，数据库有两列Col1、Col2。在存储时，按照列Col1组织各行，比如Col1已二叉树方式组织。如果查找col1中的某一个值，利用二叉树进行二分查找，不需要遍历整个数据库。这样一来列Col2就是乱序的。为了解决这个问题，为Col2建立了索引，即把Col2也按照某种数据结构（这里是二叉树）组织起来。这样子查找列Col2时只需要进行二分查找即可。

image

索引的实现

实现索引引用的数据结构和数据库一样，都是存在本地磁盘的，因此IO是个需要注意的问题。下面简单回顾一下🌲，这种数据结构。

• 二叉树
  二叉树是一种经典的数据结构，但是并不适合进行数据库索引。因为二叉树中每一个节点的度只有2，树的深度较高。在存储时，一般一个节点需要一次磁盘IO，树的深度较高，查询一个数据需要的磁盘IO次数越高，查找需要的时间越长。

• B树
  B树是二叉树的变种，主要区别在于每一个节点的度可以大于2，即每一个节点可以分很多叉，大大降低了树的深度。

image

• 每条数据表示为[key,data]
• 每个非叶子节点有(n-1)条数据n个指针组成
• 所有叶节点具有相同的深度，等于树高h
• 指针指向节点的key大于左边的记录小于右边记录

上面这些特点使得B+树的深度大大降低，并且实现了对数据的有序组织。

• B+树
  B+树是对B树的扩展，特点在于非叶子节点不存储data，只存储key。如果每一个节点的大小固定（如4k，正如在sqlite中那样），那么可以进一步提高内部节点的度，降低树的深度。

image

• 非叶子节点只存储key，叶子节点不存储指针
• 每一个节点大小固定，需要一次读磁盘操作（page）

• 顺序访问指针的B+树
  对B+树做了一点改变，每一个叶子节点增加一个指向相邻叶子节点的指针，这样子可以提高区间访问的性能。

image

• 如果没有水平的指针,B+树查找找到key=15的data，在同一个块中找到key=18的data。然后进行第二次B+查找，找到key=20的data，在同一个块中找到key=30的data。

• 有水平的指针,B+树查找找到key=15的data，查找同一个块的内容，或沿着水平指针依次向右遍历。

Sqlite中数据存储方式

• 表(table)和索引(Index)都是带顺序访问指针的B+树
• table对应的B+树中，key是rowid，data是这一行其他列数据（sqlite为每一行分配了一个rowid）
• index对应的B+树种，key是需要索引的列，data是rowid

根据索引查找数据时，分两步

1 ) 根据索引找到rowid（第一次B+树查找）
2 ) 根据rowid查找其他列的数据（第二次B+树查找）

通过两次B+树查找避免了一次全表扫描。

1. 对某一行或某几行添加PRIMARY KEY或UNIQUE约束，那么数据库会自动为这些列创建索引
2. 指定某一列为INTEGER PRIMARY KEY，那么这一列和rowid被指定为同一列。即可以通过rowid来获取，也可以通过列名来获取。

利用索引提高查找效率

比如我们有这么一个表

1 )benchmark
查询语句如下

SELECT price FROM fruitsforsale WHERE fruit=‘Peach’

由于没有索引，因此不得不做一次全表扫描。通过顺序访问指针遍历各个记录(record)，比较fruit这一列和‘peatch’是否一致，如果一致，返回这一行的price列的值

2 )对‘fruit’列加索引
如下，运行同样的语句，可以根据索引找到目标列对应的rowid为4，然后根据rowid找到对应行，从而选出price。通过两次B+树查找避免了全表查找。这也是最简单的情况

3. 多条索引命中
   建立索引时，不要求索引是uique的，即索引表中的key可以是一样的。
   如下图，索引表中有orange两条记录，找到第一条记录时，根据顺序访问指针可以轻易找到下一条索引，避免另一次B+树查找。（rowid=1和rowid=23可能位于两个不同的叶子节点中）
   即这个查找索引的过程，可以通过一次B+树查和一次next操作完成，而next操作是很快的。

4. 利用索引加快搜索和排序
   在大多情况下，我们需要同时进行查找和排序操作，这时如果建立适当的索引，可以提高查找效率。
   比如下面表中对fruit和state两列做了索引，运行下面的sql语句时，就不需要进行排序操作了，因为索引表是带有顺序的。

SELECT price FROM fruitforsale WHERE fruit='Orange' ORDER BY state

注意detail列。不用索引时，使用的是“SCAN”这个词，即全表扫描。使用索引时，使用的是“SEARCH”这个词。对于一个41G的表来说，进行全表扫描的代价显然是很大的。

优化点：

• 善用索引

<a name="designindex" id="designindex"></a>

善用索引

索引是提高数据库查询效率非常有效的手段，不过是不是所有的表都适合建索引呢？这是个值得商榷的问题。是不是所有的查询用了索引都比没用索引快？这也是值得商榷的。

什么时候不该使用索引？当一个表上建了索引之后，插入数据的速度会比不建索引的情况慢，因为在插入数据的同时还要修改索引表，有额外的开销。那如果我们在一个不会使用到索引的表上建了索引，自然就成了负担。什么样的表不需要呢？很简单，如果一个表的使用场景基本都是全表查询的（例如只做LIKE查询），那对它建索引并没有什么好处。

如何有效的使用和禁用索引呢？一般情况下，索引都是有效的，但是某些特殊的语句其实并不会使用到索引，对于这些语句，我们可以换一种写法来让索引生效，提高效率。在Sqlite中，LIKE和GLOB都是开销非常大的语句，因为它们并不会使用索引（查询字段建了索引也不会使用），都是全表查询。放着索引不用就是一种浪费，我们可以将LIKE和GLOB换成>、<之类的操作来让索引起作用，例如（x上建了索引）：

    x GLOB 'abc*'    替换成    x >= 'abc' AND x < 'abd'
    x LIKE '___'    替换成    length(x) == 3
    x LIKE 'abc_'    替换成    x > 'abc' AND x < 'abd' AND length(x) == 4

替换前后，结果相同，但是前者没有用到索引而后者用到了索引，效率会有些许差别，尤其是在数据量特别大的情况下。

怎样在特殊场景下屏蔽索引？Sqlite中，如果查询使用到索引的话，需要额外加载索引表，先查索引表再查数据表，但是如果某个查询中索引给我们带来的好处小于额外加载索引表的开销，那我们可以想办法绕开索引，例如表的记录数非常小，额外加载索引表查询反而时间更长，或者要查询的记录本来就在表的起始位置附近等。索引优化针对的是"column-name op expression"或者"expression op column-name"（op可以是<、<=、==、=、>=、>）这种格式的语句，我们只需要让条件语句不满足这个格式就可以绕开索引了，例如：

 WHERE x=5    替换成    WHERE x+0=5或者WHERE +x=5

两者结果相同，但是前者使用到了索引，后者没有使用索引，对于某些特殊场景，后者反而比前者快。

并不是所有索引都是好的，需要根据表的实际使用场景，决定是否要创建索引，创建那些字段的索引。在查询的过程中，需要注意有些语句会使用索引，有些语句不会使用索引，我们可以替换不同的写法来控制查询是否使用索引。

参考资料

Query Planning(这篇是sqlite关于索引的文档)

EXPLAIN QUERY PLAN