数据结构与算法分析 第一部分

1、企业80%的数据是非结构化或半结构化的，结构化数据仅有20%。并且全球结构化数据增长速度约为32%，而非结构化数据增速高达63%。预计今年非结构化数据占有比例将达到互联网整个数据量的75%以上。显著特征：4个“V” Volume，Variety，Value，VelocitylVolume(大量化大量化)数据体量巨大。从TB级别，跃升到PB级别；lVariety（多样化）（多样化）数据类型繁多。网络日志、视频、图片、地理位置信息等等；等等；lValue（价值化）（价值化）价值密度低。以视频为例，连续不间断监控过程中，可能有用的数据仅仅有一两秒；lVelocity（快速化（快速化）处理速度快。1秒

2、定律。大数据：正在到来的数据革命大数据：正在到来的数据革命出版时间出版时间:2012-07-01未来的十年将是一个未来的十年将是一个“大数据大数据”引领的智慧科技的时代。随着社引领的智慧科技的时代。随着社交网络的逐渐成熟，移动带宽迅速提升，云计算、物联网应用更交网络的逐渐成熟，移动带宽迅速提升，云计算、物联网应用更加丰富。更多的传感设备、移动终端接入到网络，由此产生的数加丰富。更多的传感设备、移动终端接入到网络，由此产生的数据及增长速度将比历史上的任何时期都要多，都要快。据及增长速度将比历史上的任何时期都要多，都要快。“大数据大数据”时代的脚步悄然而至。时代的脚步悄然而至。当当40亿部手机、亿

3、部手机、10亿部电脑，随时随地都在向分布在全球各地的亿部电脑，随时随地都在向分布在全球各地的服务器发送数据；当你开着车对着服务器发送数据；当你开着车对着“语音助手语音助手”说：说：“我要在附我要在附近找一家最罗曼蒂克的餐厅。近找一家最罗曼蒂克的餐厅。”之后，短短一两秒就能得到您满之后，短短一两秒就能得到您满意的答案时。其背后向您提供服务所涉及到的定位、资料检索、意的答案时。其背后向您提供服务所涉及到的定位、资料检索、存取、数据交换等一系列动作是何等的复杂。而这一系列动作正存取、数据交换等一系列动作是何等的复杂。而这一系列动作正是由是由“大数据大数据”所支撑所支撑问题一：网络架构不适应问题一：网

4、络架构不适应“大数据大数据”时代时代 传统的网络架构已经不能满足现代网络应用需求。传统的网络结构设计是以客户端向服务器发出请求，由服务器应答返回结果给客户的垂直结构。而在大数据时代，这种垂直结构的服务请求将变得越来越少，取而代之的是水平结构的横向请求服务。“大数据”时代，大量的数据都存储在分布广泛、不同地域、各种类型的服务器中。当用户发出一个搜索或查询请求时，最多的运算是服务器之间的信息交换，最后将结果返回给用户。新一代网络架构要适应Web2.0时代的水平服务应用。问题二：数据中心将面临巨大压力问题二：数据中心将面临巨大压力 “大数据”时代对数据中心的访问量是前所未有的。更多的网络设备将同时访

5、问数据中心，这包括智能手机、平板电脑、台式机、笔记本、甚至正在马路上行驶的汽车。此时，数据中心面临的压力将是难以想象的。正如铁道部去年年底推出的在线订票系统，采用的系统不可谓是当今最先进的系统，但当有几亿人同时访问的时候，网站所有服务都陷入了瘫痪。这是所有工程人员难以预料的。“大”到一定程度的时候，任何事情都可能发生。随着全球经济一体化的深入，未来数据中心要面临的不仅是一个中国地区的访问量，而是全球几十亿的访问量。还是那句话：“用户你伤不起。”问题三：数据仓库架构不适应高速反应的要求问题三：数据仓库架构不适应高速反应的要求 当今数据库里的内容不仅仅是多，而且结构已发生了极大改变，不是以二维表的

6、规范结构存储。大量的数据是非结构化的办公文档、文本、图片、XML、HTML、各类报表、图片和音频/视频等。并且在企业的所有数据中是大量且增长迅速的。企业80%的数据是非结构化或半结构化的，结构化数据仅有20%。并且全球结构化数据增长速度约为32%，而非结构化数据增速高达63%。预计今年非结构化数据占有比例将达到互联网整个数据量的75%以上。面临如此大量的非机构化数据，其移动和修改将耗费大量的人力物力，读取效率也将越来越低。当然这包括了物理存储和逻辑存储软、硬件两个层面。Data OrganizationSearch AlgorithmData StructureCreating efficie

7、nt has little to do with “programming tricks”but rather is based on good organization of information and good algorithms.A programmer who has not mastered the basic principles of clear design will not likely write efficient programs.Conversely,clear programs require clear data organization and clear

8、 algorithms.Primary MemorySecondaryStorage？外存(secondary storage)DOS核心命令处理程序内存(primary storage)快速缓存(cache)寄存器(register)20秒一个月The million-to-one ratio of disk access time versus main memory access timeFile structure is the term used for a data structure that organizes data stored in secondary memory.用

9、于组织存储在辅助存储器中数据的一种数据结构文件的存储结构即文件在外存储器中的不同组织方法 文件组织以如何能更有效地对文件进行检索和修改为原则，并考虑到存储设备条件文件组织采用什么样文件组织采用什么样的组织方式取决于对的组织方式取决于对文件进行文件进行哪些操作哪些操作和和采用采用何种外存存储介何种外存存储介质质顺序文件（Sequential File)顺序文件（Sequential File)顺序文件的存取：顺序文件的存取：根据记录的序号或记录的相对位置进行检索若存取第i个记录 ，则必须先搜索它前面的i-1个记录若插入一个新记录，则只能添加在文件的末尾若更新文件的某个记录，则必须将整个文件进行复

10、制，在复制中对要修改的记录用新记录代替批处理：批处理：在积累了一批更新要求之后，统一进行一次性处理顺序文件（Sequential File)批处理的工作原理批处理的工作原理修改请求事务文件（流水文件）排序排序有序事务文件有序主文件归并归并新新主文件主文件批处理作业示意图批处理作业示意图修改程序顺序文件（Sequential File)与顺序存储器上的存储文件处理方法相同外，还可进行随机存取随机存取可按记录号或KEY进行随机存取随机存取：若有序，可用二分查找或插值查找修改记录修改记录：若更新后的记录不比原记录大，则可在原存储位置上随机修改随机删除随机删除：采用暂作删除标记，待批处理时真正删除插入

11、记录插入记录：方法一：在每个页块中预留空闲空间，插入时只作块内移动方法二：将插入记录先存在一个附加文件中只能解决少量记录只能解决少量记录的插入的插入给查找增加麻烦，需同时查找主文件和附给查找增加麻烦，需同时查找主文件和附文件，当附文件达到一定规模时，就应做文件，当附文件达到一定规模时，就应做一次批处理，把主、附文件归并一次批处理，把主、附文件归并索引文件（Index File)主文件主文件索引表索引表关键字 指针地址1001100510061010102010221028104010011005100610101020102210281040哈希文件（Hash File)文件的散列法存取与内存

12、的散列法存取不同：文件的散列法存取与内存的散列法存取不同： 磁盘上的文件记录通常是成组存放。若干个磁盘上的文件记录通常是成组存放。若干个记录组成一个存储单位记录组成一个存储单位。“桶桶”（BucketBucket）：）：每次访问外存按每次访问外存按桶桶进行存进行存取取桶内所有记录的关键字都桶内所有记录的关键字都具有相同的散列函数值具有相同的散列函数值讨论：讨论：每个桶中页块的多少，由散列到该桶的记录数决定每个桶中页块的多少，由散列到该桶的记录数决定 桶数要适当，太少，则每桶的页块就多，增多存取时访桶数要适当，太少，则每桶的页块就多，增多存取时访 问外存的次数问外存的次数 ； 太多，则必然会有部

13、分桶只有一个页块且太多，则必然会有部分桶只有一个页块且 仅含少量记录，造成空间浪费仅含少量记录，造成空间浪费解决办法：将一些经常查找的数据项规定规定辅助关键字，并为每个辅助关键字设置一个索引表-辅助索引表辅助索引表辅助关键字值 对应链表的表头指针 链表长度单位链 职称链 数据文件0207081005060905040809100706单位 头指针 长度计算机 01 4通信 03 2机电 04 4单位索引表职称 头指针 长度助教 02 4讲师 01 3副教授 03 3职称索引表单位链 职称链 数据文件0207081005060905040809100706单位 头指针 长度计算机 01 4通信

14、03 2机电 04 4单位索引表职称 头指针 长度助教 02 4讲师 01 3副教授 03 3职称索引表优点：适合于多关优点：适合于多关键字查询，易于编键字查询，易于编程，易于修改程，易于修改 缺点：记录的插入、缺点：记录的插入、删除比较麻烦，需删除比较麻烦，需对主文件和相应的对主文件和相应的辅助索引文件中进辅助索引文件中进行相应的修改行相应的修改职称 头指针职称倒排表与多重链表文件一样，由一个主文件和多个索引表组成区别在于：辅助关键字索引的结构不同倒排文件不是将相同辅助关键字值的记录链成单向链表，而是把相同辅助关键字值的记录指针直接存放在辅助索引表中，称这种辅助索引表为倒排文件 单位 头指针

15、计算机 01，02 ,07,08 通信 03 ,05机电 04 ,06,09,10 单位倒排表助教 02 ,04,08,09讲师 01,05,10副教授 03,06,07单位 头指针优点：检索优点：检索 速度快速度快缺点：倒排文件的缺点：倒排文件的维护有一定的困难维护有一定的困难计算机 01，02 ,07,08 通信 03 ,05机电 04 ,06,09,10 单位倒排表职称 头指针职称倒排表助教 02 ,04,08,09讲师 01,05,10副教授 03,06,07在磁盘上标明一个具体信息必须用一个三维地址： (柱面号，盘面号，块号) 磁盘组磁盘组Disk pack 活动臂活动臂Activi

16、ty Arm柱面柱面cylinder磁道磁道magnetic track扇区扇区sector is the basic unit of I/O页块页块block多个扇区集结成组，形成一个块（簇cluster）-文件分配的最小单位Input Buffer（2个）36201713 14 1528 2313 17 20 3620 3613 1714 2815 2314 15 23 28Output Buffer（2个）“顺串顺串”（run）R1R2R3R4R5R6初始归并段：R1R2R3R4R5R6R12R34R56R1234R123456分析：上述归并过程中各操作所需要的时间分析：上述归并过程中各

17、操作所需要的时间R1R2R3R4R5R6R12R34R56R1234R123456归并排序时间归并排序时间tES=内排序时间内排序时间tIS假设：m个初始归并段mtIS页块存取时间页块存取时间tIO访问外存次数访问外存次数d归并时间+dtIo+Sutmg归并趟数S每趟参加归并的记录数u每做一次归并取得一个记录的时间tmgR1R2R3R4R5R6R1R2R3R4R5R6R12R34R56第一趟归并：成对地归并R1-R6 =R1R2R3R4R5R6R12R34R56第一趟归并：第一趟归并：=第二趟归并：归并第二趟归并：归并R12，R34=R1234R1R2R3R4R5R6R12R34R56第一趟归

18、并：第一趟归并：=第二趟归并：第二趟归并：=第三趟归并：归并第三趟归并：归并R1234，R56=R1234R123456合计tES= 其中，是机械动作， 想提高外排序的速度，应着眼于访问外存次数d合计tES=结论：增加归并路数k，可减少归并趟数，从而减少总的读写磁盘次数dK是否越大越好？22归并树第H层有m个记录（叶子）m=2H-1H=2采用多路归并，可减少归并的遍数如m=16即16个初始归并段，才采用4-路归并，归并遍数为2， 采用2路归并，归并遍数为4m个初始归并段的K-路归并，所需的归并遍数为kInputRun FileInputBufferRAMOutputRun FileOutput

19、 BufferIf the size of memory available for the array is M records,then the input file can be broken into initial runs of length M. Snowplow MovementExisting snowFuture snowStart time TFalling Snow例：当例：当OutBuffer满，需向磁盘写出时，须中断内部归并的执行，满，需向磁盘写出时，须中断内部归并的执行，等待写出结束后继续等待写出结束后继续 当当InBuffer空，需从磁盘上再输入一个新的页块时，

20、也须中断空，需从磁盘上再输入一个新的页块时，也须中断内部归并的执行，等待输入结束后继续内部归并的执行，等待输入结束后继续 内存与外存信息传输的时间（内存与外存信息传输的时间（I/O时间）比内部归并时间）比内部归并CPU的运行的运行时间要长得多时间要长得多内部归并经常处于等待状态内部归并经常处于等待状态所以，希望使所以，希望使 (输入输入 I ) 、内部排序、（输出、内部排序、（输出O）并行进行）并行进行例：假设有例：假设有2个归并段：个归并段：Run0=1,3,7,8,9， Run1=2,4,15,20,25 InBuffer：IB1,IB2, IB3,IB4 OutBuffer：OB0,OB

21、1方法方法1：固定缓冲区并行归并：固定缓冲区并行归并 -每个归并段固定分配每个归并段固定分配2个输入缓冲区个输入缓冲区 IB1, IB3固定分配给固定分配给Run0, IB2, IB4固定分配给固定分配给Run1 读入：读入：1324IB1 IB2归并至归并至OB0读入至读入至IB3-3-4IB1 IB278IB312OB0-IB4-OB1归并归并至至OB1读入读入至至IB4OB0写出写出采用采用2k个个InBuffer和和2个个OutBuffer，可以实现，可以实现输入、输出和输入、输出和k路内部归路内部归并的并行操作并的并行操作2k个个InBuffer若平均分配给若平均分配给k个归并段，当

22、其中某个归并个归并段，当其中某个归并段比其它短很多时，分配给段比其它短很多时，分配给它的缓冲区早早空闲，不能它的缓冲区早早空闲，不能充分利用内存区充分利用内存区例：假设有例：假设有2个归并段：个归并段：Run0=1,3,7,8,9， Run1=2,4,15,20,25 InBuffer：IB1,IB2, IB3,IB4 OutBuffer：OB0,OB1方法方法1：固定缓冲区并行归并：固定缓冲区并行归并 -每个归并段固定分配每个归并段固定分配2个输入缓冲区个输入缓冲区 IB1, IB3固定分配给固定分配给Run0, IB2, IB4固定分配给固定分配给Run1 归并至归并至OB0读入至读入至IB3-3-4IB1IB278IB3归并归并至至OB1读入读入至至IB4写出写出OB012OB0-IB4OB1-IB1IB278IB31520IB4-OB0归并归并读入读入写出写出34OB1读入：读入：-OB0-OB1-IB3-IB4-IB1IB213243-路平衡归并：路平衡归并：30912183172624513832121假设每个记录占一个物理块，则两趟假设每个记录占一个物理块，则两趟归