中国科学技术大学：《信息检索与数据挖掘》课程教学资源（课件讲稿）第4章 索引构建与索引压缩 4.1 索引构建

信息检索与数据挖掘 2019/3/71 信息检索与数据挖掘 第4章索引构建与索引压缩 一一第一讲索引构建

信息检索与数据挖掘 2019/3/7 1 信息检索与数据挖掘 第4章 索引构建与索引压缩 ——第一讲 索引构建

信息检索与数据挖掘 2019/3/73 第一讲：索引构建 ·索引构建(Index Construction或Indexing) ·构建索引的程序或计算机称倒排器（索引器，Indexer) 3

信息检索与数据挖掘 2019/3/7 3 •第一讲:索引构建 • 索引构建(Index Construction 或 Indexing) • 构建索引的程序或计算机称倒排器（索引器, Indexer) 3

信息检索与数据挖掘 2019/3/74 索引构建 (Index construction) ·思考如下问题： ·我们怎样建立一个索引？ ·对于给定的计算机内存，我们可以采用怎样的索引构建 策略？ How do we construct an index? What strategies can we use with limited main memory? 4

信息检索与数据挖掘 2019/3/7 4 索引构建 （Index construction） •思考如下问题： • 我们怎样建立一个索引？ • 对于给定的计算机内存，我们可以采用怎样的索引构建 策略？ • How do we construct an index? • What strategies can we use with limited main memory? 4

信息检索与数据挖掘 2019/3/75 索引构建 ·硬件基础 ·语料库介绍 ·索引构建算法 ·分布式索引构建 ·动态索引 5

信息检索与数据挖掘 2019/3/7 5 索引构建 • 硬件基础 • 语料库介绍 • 索引构建算法 • 分布式索引构建 • 动态索引 5

信息检索与数据挖掘 2019/3/76 典型硬件性能参数(2007年水平) 符号 含义 值 S 平均寻道时间 5ms=5x10-3s b 每个字节的传输时间 0.02μs=2x10-8s 处理器时钟频率 109s-1（也就是GHz) 底层操作时间 0.01μs=10-8s (如单词的比较或者交换) 内存大小 几个GB 磁盘空间大小 1TB或者更多 存储 (硬磁盘/SSD、内存) 计算 (CPU架构、主频) I/O(磁盘←→内存←→CPU) 6

信息检索与数据挖掘 2019/3/7 6 典型硬件性能参数（2007年水平） 符号 含义 值 s 平均寻道时间 5ms = 5 x 10−3s b 每个字节的传输时间 0.02 μs = 2 x 10−8s 处理器时钟频率 109 s −1（也就是GHz） p 底层操作时间 (如单词的比较或者交换) 0.01μs = 10−8s 内存大小 几个GB 磁盘空间大小 1TB或者更多 存储（硬磁盘/SSD、内存） 计算（CPU架构、主频） I/O（磁盘内存CPU） 6

信息检索与数据挖掘 2019/3/77 硬件基础：存储能力 ·2007年 ·IR系统的服务器通常数GB甚至数十GB的内存。 ·其可用磁盘空间大小一般比内存大小高几个(2-3)数量级 (TB级别)。 容错控制代价非常昂贵：使用许多台常规服务器要比使 。 用一台容错服务器便宜得多。 ·现在 热卖 热卖 热卖 新品 TB 218 60{a8 ￥339.00图 ￥339.00图 ￥459.00周 ￥599.00图 ￥459.00图 西部教据WD法盘1 TB SATA6GDs 希挂(Seagate)1TB72005转64M 希捷(Seagat怕)2TB7200转64M 希捷(Seagate)3TB720啭64M 西部数极WD蓝盘2 TB SATA6Gbs64M 7200装64w台式机，硬盘WD10EZ正X) SATA3台式机硬叠(ST1000DM003】 SATA3台式机硬盘(ST2000DM001) SATA3台式机硬堂(ST3000DM001) 台式机硬盘WD20EZRZ E有253029人评们 已将227111人评0 已有61307入冲价 已有22186人评 已有3664人评值 ☐对比○关注4入购物车 ☐对比关注4加入购物车 7对批○关注4加入胸物车 ☐对此心关注4加入购物车 ☐对批关注9加入购物车

信息检索与数据挖掘 2019/3/7 7 硬件基础：存储能力 • 2007年 • IR系统的服务器通常数GB甚至数十GB的内存。 • 其可用磁盘空间大小一般比内存大小高几个(2-3)数量级 （TB级别）。 • 容错控制代价非常昂贵：使用许多台常规服务器要比使 用一台容错服务器便宜得多。 • 现在 7

信息检索与数据挖掘 2019/3/78 硬件基础：存储能力(2016) 存储空间 金山无 WWW.KSYUN.COM 空间范围 价格（每月） 0-50TB(含) ￥0.17/GB 50TB-500TB(含)】 ￥0.165/GB 500TB-5000TB(含) ￥0.16/GB 5000TB以上 ￥0.155/GB 注：单位元 阿里云 aliyun.com 北京/深圳/上海 杭州 存储包 1个月 6个月（买5送1） 12个月（买9送3) 1个月 6个月（买5送1） 12个月（买9送3）】 1TB 138 690 1,242 144 720 1,296 10TB 1,375 6,875 12,375 1,436 7,180 12,924 50TB 6,876 34380 61,884 7,181 35,905 64,629 300TB 37,601 188,005 338,409 39,813 199.065 358317 500TB 62,669 313,345 564.021 66,355 331,775 597,195 8

信息检索与数据挖掘 2019/3/7 8 硬件基础：存储能力(2016) 8

信息检索与数据挖掘 2019/3/79 硬件基础：计算机I/O能力(2007) ·访问内存数据比访问磁盘数据快得多。 ·磁盘寻道：磁头移到数据所在的磁道需要一段时间， 寻道期间并不进行数据的传输。 ·因此：从磁盘到内存传输一个大数据块要比传输很多小 的数据块快得多。 ·磁盘读写操作是基于块的：从磁盘读取一个字节和 读取一个数据块所耗费的时间可能一样多。 块大小：8KB-256KB 9

信息检索与数据挖掘 2019/3/7 9 硬件基础：计算机I/O能力（2007） • 访问内存数据比访问磁盘数据快得多。 • 磁盘寻道：磁头移到数据所在的磁道需要一段时间， 寻道期间并不进行数据的传输。 • 因此：从磁盘到内存传输一个大数据块要比传输很多小 的数据块快得多。 • 磁盘读写操作是基于块的：从磁盘读取一个字节和 读取一个数据块所耗费的时间可能一样多。 • 块大小：8KB – 256KB 9

信息检索与数据挖掘 2019/3/7 10 硬件基础：1/0能力 HDD参数(2012) 四款单碟1TB硬盘的寻道时间PK 四款单碟1TB硬盘平均读写速度PK 测试软件：HD Tune/存取时间 测试软件：HD Tune:单位：MB/秒 单位：毫秒值越小越好 值越大越好 箭5T1000DM00过 1719 0453 新挂5T1000pwNM003 1569 东乏DTOLACA1O0 149.9 53 东艺DTO1ACA100 1467 CrystalDiskMark 3.0 x64 ✉口X 文件R编辑（日主题D帮助H)Language 19 日立7K1000.D 日立7K1000.D 5,1000MB,D:0%(0/93GB) AIl Read [MB/s] Write [MB/s] 206 Seq 181.7 77.72 香数WD10E2E 137 西数WD1 DEZEX 512K 178.6 77.09 10 20 29 西数WD10ZEX 日五7K1000.D东芝0101cA100510000M003 读取寻话同 20.6 189 188 144 0 100 4K 18.68 66.31 写入得港时同 137 146 153 0.458 否数WD10EZ以 日立7K1000D 东芝 DTDIACA10D .cn 4K :平均读夏速度 146.4 141 149.9 19.84 70.36 ■甲均写入速度137.9 1451 QD32 1467 泡泡网PCPOPCON 平均寻道时间：5ms (2007) 每字节的传输时间：0.02μs(2007)

信息检索与数据挖掘 2019/3/7 10 硬件基础： I/O能力 HDD参数(2012) 平均寻道时间：5ms (2007) 每个字节的传输时间： 10 0.02μs (2007)

信息检索与数据挖掘 2019/317 11 硬件基础：I/0能力 SSD参数(2014) Seq:连续做读、写硬盘检测(1024K位元组) CrystalDiskMark 3.0.1 x64 一口X 512K:随机做读、写硬盘检测(512K位元组) 文件日编辑(E)主题m帮助(H)Language 4K:随机做读、写硬盘检测(4K位元组) 5 1000MB￥ D:0%(0/233GB) 4KQD32:针对NCQ、AHCI模式做随机读写测 Read [MB/s] Write [MB/s] 6款中高端256 GB SSD性能对比 Seq 537.9 524.8 项目：CrystalDiskMark持续读写速度 512K 497.9 4092 单位：MB/秒；值越大越好 中关村在线SSD频道 4K 45.54 157.1 ■读取速度口写入速度 4K QD32 393.1 294.9 中关村在线 zoL.com.cn 三星840EV0250 GB SSD 524.8 519.1 OCZ VERTEX460 240GB SSD 519.4 0 100 200 300 400 500 600

信息检索与数据挖掘 2019/3/7 11 硬件基础： I/O能力 SSD参数(2014) 11 Seq：连续做读、写硬盘检测(1024K位元组) 512K：随机做读、写硬盘检测(512K位元组) 4K：随机做读、写硬盘检测(4K位元组) 4K QD32：针对NCQ、AHCI模式做随机读写测