IO操作
一知半解
上学的时候就听老师说数据库要减少IO次数云云，但是一直不知道IO到底什么情况下会发生
当时，我知道建立索引可以极大地加快查询速度，可能从50s变成50ms
我也知道这显然是因为减少了IO才有如此大的提升
但如果要我进一步讲，到底是哪里减少了IO，到底是怎么进行的IO，还真不清楚
最近尝试使用WordPress进行大量内容存储，得益于WordPress僵硬的数据库表结构，我有机会能够切身体会IO次数多、IO慢到底是什么滋味
也因为这个契机，进一步理解了IO在数据库中到底是怎样一个存在
谢谢你，我撇屎
查询单个值的IO
考虑以下查询：
select id from user where id=1;
假设该查询只会返回一项
我们将分别在有索引、没索引的情况下分析IO到底如何进行
没有索引
如果没有索引，数据库不知道id=1这一项到底在哪，它只能遍历整个数据库表，以查找对应的项。
但是数据库表本身是在硬盘的，因此这种情况下：
数据库需要将数据库项逐块加载到内存中，并检索id=1的项
该操作为O(n)，因此随着数据规模增大，IO的次数、查找的时间也会线性增加
有索引
什么是索引
首先需要知道，索引到底是什么？
索引是独立存储块，它以“排序”方式组织“被索引列”的值及“被索引行”的指针，以实现在数据库表中高效定位行。
说简单点，索引相当于字典、书本的“目录”
读取索引的IO
假设id为主键：primary key(id)
在有BTree索引的情况下，数据库可以通过在索引上定位id=1项所在的位置
由于索引可能很大，本身也是存储在硬盘中，因此IO主要产生在读取索引块
BTree索引查找的时间复杂度是O(logn)，因此随着数据规模增大，IO次数仅会对数级增加，是极其可观的效率提升
……
等等？这就完了吗？是不是漏了点东西？
索引只是返回目标数据块的所处地址，但数据本身还没读呢！！
这里其实分两种情况
对于目前我们考虑的查询，也就是：
select id from user where id=1;
由于我们select的项已经包含在索引中（覆盖索引），因此可以直接从索引中返回id列
也就是总共：O(logn)次IO
但如果考虑以下查询：
select id, name from user where id=1;
假设我们只有索引primary key(id)，name不在索引中，因此还需要一次额外的IO获取数据块，查询name
也就是总共：O(logn) + O(1)次IO
虽然可能很抠门，但我能不能减少这次IO？
可以的，只要索引覆盖所有select项，就可以直接返回
对于上面的例子，只要建立索引key(id, name) 就不需要额外读取数据块
但是注意，建立索引本身也会带来副作用，包括占用空间以及减慢插入删除速度，请确保建立的索引是利大于弊的
查询一堆值的IO
上述查询由于查询主键，只涉及至多1项返回项，但如果查询结果多于1项，又该如何应对呢？
考虑以下查询：
select id from user where id in (......);
其中in子句会有k项
或者以下查询：
select not_unique_id from user where not_unique_id=1;
其中not_unique_id并不唯一，会有k次命中
没有索引
什么？没有索引？那没得玩
扫描数据库表一次，记录选中的项，完事
因此它的操作仍然是O(n)
有索引
有索引的情况下，我们仍然执行索引查询，但此时需要执行k次
因此IO时间复杂度是O(klogn)
特别地，如果是非覆盖索引，我们还需要对每个数据项进行读取，如果每项数据都能1次读完，最坏情况下是k次
因此IO时间复杂度是O(klogn) + O(k)
这里有两点需要思考：
- 随着k变大，效率上会发生什么改变？
- 非覆盖索引中，什么叫最坏情况下读取k次？最好情况又是什么？
大量返回数据的效率
第一个思考问题，随k变大，索引的优势逐渐降低
最极端情况下，如果返回的结果是全表，那么带索引的IO时间复杂度退化为O(nlogn)，这甚至比全表扫描还慢得多
当然，数据库绝对不会在这种情况下使用索引，不过这也给了我们一个警示：
如果返回的数据量非常大，将不可避免地进行多次IO，此时优化的幅度有限，此时应该考虑：
- 是否真的需要返回这么多数据？
- 能不能使用缓存？
- 数据的存储方式（表的设计）是否合理？
- 关系型数据库是否是一个合适的选择？
- 是不是该升级你的服务器了（）？
没错……想要进一步优化，只能在查询之外做优化，因为查询的瓶颈是“返回的数据量”，是在不改变前提的情况下无法规避的
非覆盖索引的时间常数优化
第二个思考问题
上面说到，非覆盖索引最坏情况下需要O(klogn) + O(k)次IO
但可以利用聚集补救一下
如果我们查询的数据在物理位置上非常相邻，我们就可以在一次数据块读取中读到多条数据，此时总IO次数会向最好情况的O(klogn) + O(1)趋近
虽然时间复杂度没有真正减少，但是如果k非常大，而且没有其它好的优化方法，将数据聚集起来还是很有帮助的
什么情况下聚集可以优化查询速度？
一般情况下，主键是聚集索引
对于一个自增主键，如果你的查询形如：
select * from user where id in (1,2,3,4,5,6,7,8,9,10);
select * from user where id in (10,9,8,7,6,5,4,3,2,1);
这两个查询的索引值邻近，由于聚集索引的物理连续性，能从一次IO中读取多条相邻数据
但如果形如：
select * from user where id in (100,200,300, ...);
查询id非连续，这种情况百分百是需要读取k个数据块
阿哲，那怎么聚集？
聚集也具有一定局限性：
- 因为涉及物理存储，因此只能有一种聚集，一个聚集索引
- 你的数据“逻辑上”能够聚集，否则没有意义，因为你无法将它应用在任何查询
如果你恰好有这么一种数据，不妨专门为它建立聚集索引，以抢救一下超长时间查询
打个比方：
假设每个用户都会有一个not_unique_id标签，我们希望查询所有该值为1的用户：
select * from user where not_unique_id=1;
如果该查询是频繁操作，我们可以为该列建立聚集索引：
PRIMARY KEY(not_unique_id, -- 聚集同一not_unique_id的所有行
id), -- 使primary key唯一
KEY(id), -- 让id项的 AUTO_INCREMENT 继续生效
但不要对这个做法抱有太高期望，因为它并没有从时间复杂度上优化查询
小结
现在我终于理解数据库中的IO是如何进行的
也认识到一次查询中可能涉及成百上千次IO
我们可以使用索引从时间复杂度级别上降低IO
但对于返回大量结果的查询而言，任何优化都很难产生质变
没错，一个重要的事实是：关系型数据库不适合做大量返回的操作
也许下次，应该思考：
- 是否应该减少返回的数据规模
- 是否应该缓存数据
- 是否应该换一种形式组织数据
- 甚至是否应该使用关系型数据库存储它
