除了词典,生活中随处可见索引的例子,如火车站的车次表、图书的目录等。它
们的原理都是一样的,通过不断的缩小想要获得数据的范围来筛选出最终想要的
结果,同时把随机的事件变成顺序的事件,也就是我们总是通过同一种查找方式
来锁定数据。
数据库也是一样,但显然要复杂许多,因为不仅面临着等值查询,还有范围查询
(>、<、between、in)、模糊查询(like)、并集查询(or)等等。数据库应该选择
怎么样的方式来应对所有的问题呢?我们回想字典的例子,能不能把数据分成段,
然后分段查询呢?最简单的如果 1000 条数据,1 到 100 分成第一段,101 到
200 分成第二段,201 到 300 分成第三段……这样查第 250 条数据,只要找第
三段就可以了,一下子去除了 90%的无效数据。但如果是 1 千万的记录呢,分
成几段比较好?稍有算法基础的同学会想到搜索树,其平均复杂度是 lgN,具有
不错的查询性能。但这里我们忽略了一个关键的问题,复杂度模型是基于每次相
同的操作成本来考虑的,数据库实现比较复杂,数据保存在磁盘上,而为了提高
性能,每次又可以把部分数据读入内存来计算,因为我们知道访问磁盘的成本大
概是访问内存的十万倍左右,所以简单的搜索树难以满足复杂的应用场景。
磁盘 IO 与预读
前面提到了访问磁盘,那么这里先简单介绍一下磁盘 IO 和预读,磁盘读取数据
靠的是机械运动,每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输
时间三个部分,寻道时间指的是磁臂移动到指定磁道所需要的时间,主流磁盘一
般在 5ms 以下;旋转延迟就是我们经常听说的磁盘转速,比如一个磁盘 7200
转,表示每分钟能转 7200 次,也就是说 1 秒钟能转 120 次,旋转延迟就是
评论0
最新资源