专栏首页Apache IoTDB索引 vs 全表扫描

索引 vs 全表扫描

索引是数据库的重要技术,本质是用空间换时间,或者放慢写入加速查询。通常我们会将索引和全表扫描来对比,并且一般都会觉得全表扫描很 low,真的是这样吗?

之前我们介绍了第一个文件格式:什么是文件格式? 在这个文件格式里,数据没有排序,顺序存储,我们只提供了查询所有数据的接口,当我们想进行值过滤时,比如查询大于10的数据,需要将所有数据遍历一遍,如果把这个文件看做一个只有一列的表,这种查询方式就叫全表扫描。

磁盘结构和基本耗时

磁盘的组织结构 盘片->磁道->扇区。由于盘片是并行操作的,因此可以忽略寻找盘片的时间。所以基本上要找一个数据需要找到对应的磁道(类似树的年轮),再找对应的扇区(一段扇形)。

磁盘性能的主要度量指标有以下几个:

访问时间:从发出读写请求到数据开始传输之间的时间。也就是磁盘定位数据的时间,在程序中就是那个 seek。访问时间包括寻道时间(找磁道)和旋转等待时间(找扇区)。一般在几毫秒级。

数据传输率:在定位数据之后。就开始将数据从磁盘和内存之间传输了。这个时间一般每秒几十MB。

顺序访问 vs 随机访问

磁盘上的文件是一块一块组织的,这里的块(block)是逻辑概念,可能512字节到几KB。从磁盘读数据需要一块一块读。即使你只读1Byte数据,也会读一块。

顺序访问:连续访问磁盘相邻的块。这样磁盘只需要一次磁盘寻道。

随机访问:随机访问磁盘不同位置的块,一般每次只读少量数据。这样磁盘每处理一个随机访问请求就需要一次磁盘寻道。随机访问的效率远低于顺序访问。

存储模型

硬件:磁盘数据传输率记做 T,平均访问时间记为 S。

数据:一个包含 N 个数据的数据集,数据是可比较的。数据在磁盘上无序存储,数据均匀分布。每个数据所占空间为 X,那么数据的总大小为 NX。

这张图表示数据在磁盘上的存放顺序:

索引:在数据上建立索引,索引可以看成数据的一种映射,一种表示方式。可以全部放在内存中,并且精确定位原始数据。

查询流程

查询模式:查询有过滤条件,假设过滤条件的选择度为 F,意思是查询结果集占总数据量的 F 倍,F 处于 [0,1] 之间。

现在有两种查询方式:全表扫描、索引。全表扫描和索引都是逻辑概念。

全表扫描:最简单的查询操作。即将数据从磁盘上一个个读到内存中做过滤,最后返回结果。这种方式的特点是不管数据有没有用,都先读出来,磁盘读取数据总量大,但是seek只有一次。对应磁盘的顺序访问

黄色表示需要从磁盘读到内存中的数据,全表扫描时候就是这样:

全表扫描总耗时 = IO耗时 = NX/T

索引:由于磁盘上数据是乱序的,我们建一个B+树索引,并在内存中维护索引,索引将所有数据排序,并记录对应的磁盘位置。在查询时,首先在索引上过滤出所有结果集在磁盘上的位置,再到磁盘上去精确读取结果集。这种包括少量的磁盘IO+大量的 seek。对应磁盘的随机访问

效果图如下图:磁盘的操作为定位一个数据,读取,再定位下一个数据......

Seek耗时:NFS

IO耗时:NFX/T

索引查询总耗时 = Seek耗时 + IO 耗时 = NFS + NFX/T

比较

接下来看看这些参数,在不考虑更新硬件时,磁盘吞吐率 T、平均访问耗时 S、数据量 N、每个数据大小 X 都是常量,没得改。

一共就 NTFSX 五个参数,接下来只有 F 了,这个东西是个变量,取决于查询过滤条件。比如你想查身高150以上的男生,这个过滤条件就没啥区分度,可能 F=0.8,大部分都会被选出来,但是如果查190以上的男生,可能 F=0.1,只有一小部分会被选出来。

有区别就有不同的应对措施,我们可以根据 F 选择查索引还是全表扫描。直接算一下什么时候索引查询比全表扫描快,也就是下边这个式子:

NFS + NFX/T < NX/T

即:F < X / (TS+X)

可以看到,跟总数据量没关系,当 F 足够小的时候,选择索引比较好。如果结果集比较多,seek过多,那么全表扫描是更优的。

例子

举个实际例子感受一下:

平均Seek时间: S=5 ms

磁盘吞吐率:T=300 MB/s

单个数据大小:X=128 Byte

这个时候,过滤条件的选择度需要小于 0.008%。

总结

传统数据库中一般对索引的介绍是,当表很大的时候可以考虑建立索引。Seek是一个很耗时的操作,需要避免查询中过多的 seek。同时,数据库应该根据不同的查询条件选择查询方式。

本文分享自微信公众号 - IoTDB漫游指南(Apache-IoTDB),作者:铁头乔

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Apache IoTDB 发布 0.10.0!

    参考:https://raw.githubusercontent.com/apache/incubator-iotdb/release/0.10.0/RELEA...

    Apache IoTDB
  • java 字节流入门(读文件)

    从磁盘到内存的流程大体介绍完了,本文主要介绍读文件中的坑,在实际系统中,如果不注意这些小坑,有可能导致系统挂掉。

    Apache IoTDB
  • 大数据与大数据计算

    今天听了一场报告会,是清华计算机系60周年系列讲座之一,主讲人是哈工大软院院长李建中教授,主题《计算和数据资源受限的大数据计算的复杂性理论与高效算法研究》,李老...

    Apache IoTDB
  • 小教程:​列出Ubuntu上的磁盘

    在本文中,我将向您展示如何从Ubuntu中列出连接到您的计算机上的磁盘(即ssd、HDDs、u盘)。

    用户6543014
  • 【DB笔试面试705】在Oracle中,ASM磁盘有几种冗余方式?

    ASM使用独特的镜像算法,它不镜像磁盘而是镜像盘区。一个磁盘组可以由两个或多个故障组(FAILGROUP)组成,一个故障组由一个或多个ASM磁盘组成。故障组提供...

    小麦苗DBA宝典
  • ASM 翻译系列第一弹:基础知识 ASM AU,Extents,Mirroring 和 Failgroups

    原作者:Bane Radulovic 译者: 魏兴华 审核: 魏兴华 ASM Allocation Units 在ASM磁盘组中,最基本空间分配单位...

    沃趣科技
  • 每周学点大数据 | No.21磁盘算法概述

    No.21期 磁盘算法概述 Mr. 王:现在我们谈谈磁盘算法的问题。根据你的了解,跟我说说计算机中都采用了哪些种类的存储器? 小可:这个我还是略知一二...

    灯塔大数据
  • [Oracle ASM全解析]ASM镜像和磁盘组冗余

    ASM可以为ASM 文件提供镜像服务,做法为将不同的文件区拷贝放在故障组中,这样可以保证文件副本不会存放在同个故障组中

    bsbforever
  • 0678-6.2.0-如何在CDH中使用HDFS分层存储

    在前面的文章中,Fayson介绍过什么是HDFS分层存储,参考《6.2.0-什么是HDFS分层存储》。这个功能很早CDH就支持了,本文基于CDH6.2实际演示如...

    Fayson
  • WaveSense的探地雷达可以使自动驾驶汽车在恶劣天气中更安全

    雷达,激光雷达,摄像头,它们是帮助优步自动驾驶汽车,通用汽车的Cruise Automation,Waymo以及其他对周围环境感知的组件。但WaveSense首...

    AiTechYun

扫码关注云+社区

领取腾讯云代金券