漫谈有序读取与关系库索引

个人随笔 (Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu)

从有序读取对速度的影响，到关系库索引建立的方法用途，写写自己当前的了解。
不过也只能称为漫谈了，因为内容组织的有点乱，并没有什么完整的主题和逻辑。

KV的有序读取

在一个KV数据库中，如果检索数据的key是顺序的，则能有一个惊人的查询速度，这背后的原因就来源于数据的有序存储，block-cache，block的有效读放大，磁盘的预取，磁盘的硬件特点。

KV数据库的内容存储排序很彻底：
文件内是有序的-block排序存储；block内也是有序的；这就为顺序查询时带来更大的IO吞吐量。

下面以leveldb-sstable的结构为例

// sstable file
[data block 1]
[data block 2]
[data block ..]
[data block n]
[filter block]
[meta index block]
[index block]
[footer]

// block 
[key 1, value 1]
[key... value...]
[key n, value n]
[restart array]
[block trailer]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

关系数据库的有序读取

对于关系型数据库来说，比如常用的mysql，B+树结构，B+树也是排序树，按照排序键值取数据的话，则node-cache，node的读放大都会起到正向的作用。

对于关系数据库来说，node节点之间不是顺序排序存储到磁盘的，按照页面进行分布存储，但也大概率会有一定的顺序性；顺序读取时，可能不及KV，但也能有一个较大的IO吞吐量。

B+树的上层节点与叶子结点，各自都是连续存储在磁盘的页面上，它们之间虽然非连续，但在结点内是排序的+连续存储的。

注：关系库未做详细研究，为推测情况

// b+ tree node contents
[keys range 1, node 1/page]
[keys range 2, node 2/page]
...
[keys range n, node n/page]

// b+ leaf node contents
[key 1, contents 1]
[key 2, contents 2]
... 
[key n, contents n]
1
2
3
4
5
6
7
8
9
10
11

关系库的索引

再来考虑关系数据库索引的意义：
关系库数据放入时，有一个主存储索引的存在，也即聚簇索引，这个数据放入时会形成一颗索引树，并确保了数据存储时的排序，叶子节点中数据放置按此排序。

推测添加索引情况：我们为表添加索引或唯一索引时，会再建立一个B+索引树，这颗索引树建立时，按照聚簇索引遍历数据，把新加索引字段取出来，建立一棵新的B+树，形成索引字段指向。当采用新加索引字段查询时，会遍历这个新的B+树，来找出对应记录。

实际查资料看到：mysql的innodb的新加索引作为一种辅助索引存在，使用时涉及两次索引查询，一次该索引查询，一次聚簇索引查询。
新加索引的B+树，查到的数据部分是聚簇索引的键值，查到后，再查聚簇索引找到数据。
这样的好处是，新建的索引和数据存储没有了关系，后续的数据移动等，都和该索引没有关系，新加索引类似一个索引字段到主键的索引。

对于无索引情况：当查询字段没有索引时，就只能采用聚簇索引遍历数据，逐个来做字段对比。无索引可用与有索引可用对比，无索引IO占用又大，效率又没有直接定位到叶子节点高。

个人随笔 (Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu)