数据结构（从概念到算法）.ppt

*********************************************************************************************************************************************************************************************************************************************************************************************************************************************************************大数据存储9.2.4HBase数据库HFile是Hadoop的二进制格式文件，实际上StoreFile就是对HFile做了轻量级包装，即StoreFile就是HFile。HFile内部结构示意图如下图所示。其中，Data为数据块，保存的是表中的数据，可以被压缩；Meta为元数据块，保存用户自定义的键值对，也可以被压缩；FileInfo是HFile的元数据信息，用户也可以在这一部分添加自己的元信息；DataIndex是存储Data块索引信息的块文件，每条索引的key是被索引block中第一条记录的key；MetaData是存储Meta块索引信息的块文件；Trailer是HFile的最后一部分，它用来存储FileInfo、DataIndex、MetaIndex块的偏移量和寻址信息。03PART大数据检索传统意义上的索引，其目标是加快查询速度。索引是独立于数据的，它通常可以被加载到内存中，这样就可以高效地进行数据访问，例如典型的B树等。但是在大数据中，这一点就变得不太现实。即使索引比实际数据小很多，但由于实际数据的规模非常大，索引量依然会很大，因此索引仍然无法全部被放入内存，这样就导致很多传统数据库的索引模式对大数据失效。关系型数据库一般采用B+树作为索引的数据结构。在关系型数据库中，数据随机无序写在磁盘上，B+树能够很好地提高数据库的读数据能力。对于大型分布式数据系统，B+树的性能就没那么强了；这种情况下，日志结构合并树（LogStructuredMergeTree，LSM树）是一个更好的选择。9.3.1大数据索引大数据检索LSM树是一种分层、有序、面向磁盘的数据结构。LSM树的核心思想是以放弃部分读数据能力来换取写入能力的最大化。使用LSM树，假定内存足够大，因此不需要每次更新数据时就必须将数据写入磁盘，而是将必威体育精装版的数据驻留在内存中，等积累到阈值后再使用归并排序的方式将内存中的数据归并且追加到磁盘队尾。事实上，所有待合并的树都是有序的，因而我们可以通过合并排序的方式将它们快速合并到一起。LSM树的原理是把一棵大树拆分成N棵小树，即将它写入内存中，随着不断更新数据，小树越来越大，达到一定的阈值之后，内存中的小树会被写回到磁盘中，磁盘中的树可定期做归并操作，归并成一棵大树，以优化读性能。LSM树合并示意图如图所示。9.3.1大数据索引大数据检索LSM树与B树的差异就体现于在读性能和写性能之间进行取舍，在牺牲性能的同时，寻找其他方案来弥补。LSM树具有批量特性，可实现存储延迟。当写操作大于读操作时，LSM树相较于B树有更好的性能。这是因为随着插入操作的增多，为了维护B树结构，结点需要分裂，读磁盘的随机概率会变大，性能会逐渐减弱。LSM树的数据更新只在内存中操作，没有磁盘访问环节。如果读取的是最近访问过的数据，则可以直接从内存中读取，减少了磁盘访问，因而提高性能。9.3.1大数据索引大数据检索大数据检索技术是科学家一直都在研究的内容，有哪些信誉好的足球投注网站引