数据库概论--数据库存储.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,提纲,物理存储介质,RAID,缓冲区管理,存储结构,索引,大数据存储,物理存储介质,物理存储介质,高速缓冲存储器（cache）,最快最昂贵的存储介质,很小，由操作系统管理,主存储器（mainmemory）,存放可被处理的数据的存储介质,易失，相对整个数据库太小,快闪存储器（flashmemory）,读性能类似主存，写速度非常慢,电子可擦除可编程只读存储器(Electrically,ErasableProgrammableRead-OnlyMemory),物理存储介质,磁盘存储器（Magnetic-diskstorage）,直接读取设备，支持随机读取,非易失联机数据存储设备,访问数据时，磁盘内存；修改后的数据，内存,磁盘,光学存储器（Opticalstorage）,只读(CD-ROM)、一次写多次读(WORM)、多次写,(CD-RW),磁带（tape）,顺序访问，归档存储，容量大，价格便宜,磁盘,磁盘,基本构成,盘片(platter)、磁道(track)、扇区(sector)、柱面,(cylinder),读写头(read-writehead)：反转磁性物质磁化的方向,磁盘臂(diskarm),磁盘控制器(diskcontroller)：接受读写扇区命令，定,位读写头。向扇区写入数据时附加校验和,(checksum)，读取时重新计算校验和,磁盘,磁盘性能度量,：从发出读写请求到数据开始传输之间,访问时间,磁盘臂，,移动,的时间。为到达指定扇区，需要先,定位到正确的磁道，然后,旋转,磁盘，直到指定的,扇区出现在读写头下方,寻道时间,(seektime)：磁盘臂重定位时间，取决,于目标磁道和磁盘臂当前距离，230毫秒。平均,寻道时间是最大寻道时间的1/3,旋转等待时间,(rotationallatencytiime)：目标扇区,旋转到读写头下面的时间，每转在411毫秒之间。,平均旋转时间是旋转一周的1/2,数据传输率,(data-transferrate)，25100兆/秒,磁盘访问优化,磁盘块的大小,小，更多的磁盘传输次数；大，空间浪费,调度,块在一个柱面上，按块经过读写头的顺序访问；块在不同,柱面上，按使磁盘臂移动距离最短的顺序访问,电梯算法,文件组织,按与预期数据访问方式最接近的方式组织磁盘块,碎片整理,日志磁盘,顺序写，消除了寻道时间,检查点,RAID,廉价磁盘冗余阵列（RAID）,RedundantArraysofInexpensiveDisks,是一种利用大量廉价磁盘进行磁盘组织的技术,上，大量廉价的磁盘比少量昂贵的大磁盘合,价格,算得多,上，使用大量磁盘可以提高数据的并行存取,性能,上，冗余数据可以存放在多个磁盘上，因,可靠性,此一个磁盘的故障不会导致数据丢失,过去RAID是大而昂贵的磁盘的替代方法；今天，,使用RAID是因为它的高可靠性和高数据传输率；,因此“I”代表independent，而非inexpensive,冗余,通过冗余提高可靠性,N个磁盘组成的集合中某个磁盘发生故障的概率比,特定的单个磁盘发生故障的概率高很多,假定单个磁盘的MTTF是100,000小时(约为11年)，,则由100个磁盘组成的阵列的MTTF是1000小时(月,为41天),冗余（Redundancy）,存储额外的信息，以便当磁盘故障时能从中重建,镜像冗余,一个逻辑磁盘由两个物理磁盘组成，写操作在每个磁,盘上执行,如果其中一个发生故障，数据可以从另一个磁盘读出,只有第一个磁盘的故障尚未恢复，第二个磁盘也发生,故障，这时才会发生数据丢失,假定一个磁盘的MTTF是100,000小时，修复时间是,10小时，则镜像磁盘系统的MTTF是100,000,2,/,（2*10）=500*10,6,小时，约为57000年,校验码冗余,纠错码（ECC：Error-Correcting-Codes）,内存中每个字节都有一个奇偶校验位与之相连，,它记录这个字节中为1的比特位的总数是偶数（=0）,还是奇数（=1），如果字节中有一位被破坏，则,字节的ECC与存储的ECC就不会相匹配；通过ECC,可以检测到所有的1位错误,11110000,0,10101110,1,00111000,0,拆分,将数据拆分到多个磁盘上以提高传输率,通过并行提高性能,负载平衡多个小的存取操作（即页面存取），提高,以提高这种存取操作的,吞吐量,响,并行执行大的存取操作，以减少大的存取操作的,应时间,拆分,比特级拆分（Bit-levelstriping）,将每个字节按比特分开，存储到多个磁盘上,例如，对于一个由8个磁盘组成的阵列，将每个字,节的第i个比特位写到第i个磁盘上；它的存取速度,是单个磁盘的8倍,对于由4个磁盘组成的阵列，将每个字节的第i个比,特位和第i+4个比特位写到第i个磁盘上,块级拆分（Block-levelstriping）,对于由n个磁盘构成的阵列，文件的第i块存放在,第(imodn)+1个磁盘上,RAID级别,镜像提供高可靠性，拆分提供高数据传输率，,通过利用与奇偶校验相结合的磁盘拆分想法，,可以实现以较低成本提供冗余的方案,不同的RAID级别，具有不同的代价、性能和,可靠性,C,P,代表数据的第,表示纠错位,二个拷贝,RAID0,块级拆分且没有任何冗余（如镜像或奇偶校验,位）的磁盘阵列,用于高性能访问并且数据丢失不十分重要的应,用场合,RAID0：无冗余拆分,RAID1,带块级拆分的磁盘镜像,提供最佳写性能,一般用于类似于数据库系统中日志文件存储的,应用场合,C,C,C,C,RAID1：无冗余拆分,RAID3,磁盘控制器能够检测一个扇区是否被正确的读出,如果一个扇区被破坏，对扇区的每一位，通过计算其,他磁盘上对应扇区的对应位的奇偶值来推断该位是1,还是0。如果其余位的奇偶值等于存储的奇偶值，则,丢失的位是0，反之为1,使用N道数据拆分的RAID3对一个字节的读写散布在,多个磁盘中，因此读写一个块的传输率是使用N道数,据拆分的RAID1的N倍,所有磁盘参与每个I/O请求，RAID3支持的每秒I/O,数较少,P,RAID3：位交叉奇偶校验,RAID3,生成校验盘,故障恢复,D111110000,D210101010,D300111000,D111110000,D2?,D300111000,D401100010,D401100010,D210101010,RAID3,写操作,D210101010,D211001100,D210101010,D211001100,D111110000,D211001100,D300111000,01100110,D401100010,D400000100,读D1,D3，写D2,D4,读D2,D4，写D2,D4,RAID4,块级拆分，在一个独立的磁盘上为其他N个磁,盘上对应的块保留一个奇偶校验块,读取一个块只访问一个磁盘,每个存取操作的传输率低，但可以并行地执行,多个读操作，从而产生较高的总的I/O率,读取大量数据的操作有很高的传输率，因为所,有磁盘可以并行地读,P,RAID4：块交叉奇偶校验,RAID4,D111110000,D210101010,D300111000,D401100010,RAID4,读数据：一种潜在的并行,假定D1忙，其余磁盘空闲,D210101010,D300111000,D401100010,D111110000,RAID5,将数据和奇偶校验位分布到所有的N个磁盘上,奇偶校验块不能和这个块对应的数据存储在同,一个磁盘上,所有磁盘都参与对读请求的服务，而RAID4中,奇偶校验磁盘不参与读操作,RAID5包容了RAID4，同时在相同成本下，提,供了更好的读写性能,P,P,P,P,P,RAID5：块交叉的分布奇偶校验,RAID6,D1D2D3D4,D5D6D7,1110100,1101010,1011001,Hammingcode,D5对应D1,D2,D3,D6对应D1,D2,D4,D7对应D1,D3,D4,RAID6,生成校验盘,D111110000,D210101010,D300111000,D401000001,D501100010,D600011011,D710001001,RAID6,故障恢复,D111110000,取D1,D4,D6,D2?,D300111000,D401000001,D210101010,取D1,D2,D3,D5?,D600011011,D710001001,D501100010,RAID6,写操作,D210101010,D200001111,D210101010,D200001111,10100101,D501100010,D600011011,D511000111,D610111110,高性能,可靠性差,最佳写性能,开销大,高数据传输率,大数据量,高的总I/O率,适合随机读,大数据量,高可靠性,选择合适的RAID级别,RAID1orRAID5?,依赖于读/写的比率,为写1块数据，RAID5需要2块读和2块写,如果应用需要每秒r次读，w次写,RAID1要求每秒r+2w次I/O操作,RAID5要求每秒r+4w次I/O操作,RAID5比RAID1使用较少的磁盘可能是幻觉,记住：当写操作较少并且数据非常大时，RAID,5较优，否则RAID1更佳,选择合适的RAID级别,RAID0,无冗余拆分,RAID1,镜像,RAID5,拆分校验码,RAID10,先镜像、后拆分,RAID01,先拆分、后镜像,选择合适的RAID级别,日志文件,RAID1,容错，高写输出率,临时文件,RAID0isappropriate.,无容错，高吞吐率,数据以及索引文件,RAID5适合于读为主的应用,RAID10适合于写为主的应用,磁盘还是内存,保持常用数据在内存，可以减少磁盘I/O，但,增加内存代价,若一个页面每秒被访问n次，将它驻留在内存节省,price-per-disk-drive,n*,accesses-per-second-per-disk,保持一个页面在内存的代价,price-per-MB-of-memory,pages-per-MB-of-memory,磁盘还是内存,5-minuterule：,如果一个被随机访问的页面,的使用频率超过每5分钟一次，那么它应该被,驻留在内存,1-minuterule：,如果被顺序访问的页面的使,用频率超过每1分钟一次，那么它应该被驻留,在内存,price-per-disk-drive=2000$/disk,accesses-per-second-per-disk=64accesses/second/disk,price-per-MB-of-memory=15$/MB_RAM,pages-per-MB-of-memory=128pages/MB,2000*128/15/64/=266,缓冲区管理,当需要访问一个磁盘块时,如果该块已在缓冲区中，返回块在内存中的地址,如果块不在缓冲区中,缓冲区管理器为该块在缓冲区中分配空间，如,果有必要，替换缓冲区中的其他块,如果被替换的块被修改过，则将其写回磁盘,将所需块调入缓冲区，返回其在缓冲区的地址,缓冲区管理,被钉住的块(pinnedblocks),不允许写回磁盘的块,当一个块上的更新正在进行时，不允许写回磁盘,钉住被频繁访问的小表,块的强制输出(forcedoutputofblocks),先写日志原则,检查点,提交事务的日志记录,Sys.dm_os_memory_clerks,缓冲区管理,：替换策略,LRU(最近最少使用),如果必须替换一个块，则替换最近最少使用的块,MRU(最近最常使用),如果必须替换一个块，则替换最近最常使用的块,对于R中的每条元组tr,对于S中的每条元组ts,RS,一旦R中的一个元组处理完，就不会再使用它了，应该立即,丢弃(tossimmediate),当,S中的元组都被处理完后才会再用到它，应该采用MRU,S中的一个元组被处理完，只有其他,缓冲区管理,：SQLServer,访问内存页面,为快速找到页面，内存页面地址被散列,给定dbid-fileno-pageno标识(数据库ID,文件号、,页面号的组合)，计算其hash地址,Lazywriter(缓冲池管理器),NUMA,使用时钟算法,每个缓冲池有一个计数器，当有进程访问该缓冲,池时，计数器加一,当需要Lazywriter扫描每个缓冲池，如果其计数器,为0，则释放该空间（如果发生修改，则写回磁,盘）；如果计数器不为0，则计数器减一,SQLServer存储结构,文件结构,表结构,行结构,SQLServer存储结构,数据库,物理上,逻辑上,区间,文件组,页,操作系统文件,文件,一个数据库是操作系统文件的集合,数据库之间不能进行文件共享,一个数据库至少包括一个数据文件和一个日志,文件,每个数据库最多32,767个文件,驱动器不能是压缩的,数据和日志文件不能放在同一驱动器上,文件,文件类型,主数据文件-.mdf每个数据库一个,目录表sysfiles1必须完全包含在此文件中,辅助数据文件-.ndf零个或多个,日志文件-.ldf一个或多个,包含事务日志,.mdf总是文件1，第一个日志文件是文件2,文件组,许多文件可以形成一个命名的文件组进行统一,的分配和管理，提供了灵活性,组号1是主组号,每个数据库中都存在,包含数据库的系统表,日志文件不加入文件组,每个数据库最多256个文件组,一个文件组包含多个文件，一个文件只属于一,个文件组,一个文件组包含多个对象，一个对象只属于一,个文件组,SQLServer存储结构,如何为对象分配空间？,GAM,SGAM,PFS,如何找到对象占据的空间？,IAM,行在页内是如何存储的？,页面,数据文件被划分成8k的页面,每个文件中的页面号都以0开始,页面号的形式为(file#:page#)，如(3:124),区间,8个连续页面构成一个区间-64k,总是从能被8整除的页面开始,第一个区间,区间0,位于文件1，包含页面0到7,第二个区间,区间8，包含页面8到15,存储分配总是按照区间为单位进行,对象每次增长1个区间,I/O可以按页面(8KB)或者区间(64KB)来进行,区间,单一区间：区间被单一对象拥有,混合区间：区间被多个对象共享(最多8个),对象的头8个页面从混合区间中分配,ExtentAn8KpageMixedExtent,(8pages=64K),081624,32,40,T1,T2,T1,T3T4,T3,T4,dbccextentinfo(northwind,orders,1),GAM全局分配位图,记录文件当中哪些区间已经被分配的页面,可以看成是一个8000个字节的位图,每个位代表一个区间,位0代表区间0，位1代表区间8，位2代表区间16,0：被使用,1：未被使用,差不多64,000位，所以可以表示64,000个区间,表达4GB(3,994MBs)数据空间,如果文件大于4GB，可以增加新的GAM页,第一个GAM位于文件的第三个页面(page2),下一个GAM位于第511,232个页面,GAM总是位于它所控制范围的第一个页面,SGAM共享全局分配位图,用于表示文件中哪些区间被作为共享区间分配并且仍,然有空闲区间可供分配,结构与GAM相同,每一位代表一个区间,位0代表区间0，位1代表区间8，位2代表区间16,0：区间要么不是共享区间，要么共享区间没有空闲页,1：区间是共享区间，并且至少有一个空闲页,表达4GB数据空间，与对应的GAM表达范围相同,如果文件大于4GB，可以增加新的SGAM页,第一个SGAM位于文件的第四个页面(page3),下一个SGAM位于第511,233个页面,GAM与SGAM,CurrentUseofExtent,GAMBitSetting,SGAMBitSetting,Free,notinuse10,Uniformextent,orfullmixedextent00,Mixedextentwithfreepages01,如果需要一个新的、完全没有使用的区间，可,以从GAM中寻找位为1的区间,如果需要一个有空闲页的混合区间，可以寻找,在GAM中位为0、在SGAM中位为1的区间,PFS空闲页空间,记录文件中每个页面是否已经被分配以及有多,少空闲空间,每一个页面在PFS页中有一个字节对应,每个PFS覆盖8088个连续页面(64MB),页面充满度：0,1-50%,51-80%,81-95%,96-,100%,第一个PFS位于文件的第二个页面(page1),以后每8088都是一个PSF页,IAM索引分配位图,如何发现一个特定对象的区间或页面？,每个表/索引都至少有一个IAM，记录该对象拥,有哪些区间,一个对象每占据文件的4G空间，就需要一个,IAM，对象的所有IAM构成一个双向链表,一个对象的IAM被随机安放在文件中,对象的第一个IAM记录在sysindexes.firstIAM中,IAM索引分配位图,一个IAM包含一个头、8个页面指针槽、一个,表示文件内区间范围的位集合,头表示该IAM所映射的头一个区间的地址,8个页面指针槽表示在一个混合区间内哪些页面属,于该对象,IAM覆盖的范围与GAM相同，如果位为1，说明该,区间被分配给该对象，如果位为0，说明该区间未,被分配给该对象,如11000000，说明第一、二个区间被分配给该对,象,DCM-差异变化位图,记录自从上次完全数据库备份之后，哪些区间,发生了变化,DCM位于文件的第7个页面(page6),DCM与GAM结构和表达范围相同,每次进行完完全数据库备份，DCM所有位被置,为0，以后如果区间的任何页面发生修改，,DCM对应的位置为1,当进行差异数据库备份时，将对应DCM中位为,1的区间备份出去,BCM批量变化位图,记录当发生批量更新操作(BULKINSERT,bcp,selectinto,createindex等)时，哪些区间发生,了变化，BCM对应的位置为1,BCM位于文件的第8个页面(page7),BCM与GAM结构和表达范围相同,每次进行完完全数据库备份或日志备份，BCM,所有位被置为0,当进行批量日志恢复时，将对应BCM中位为1,的区间恢复,表信息存储,Sysobjects,name,objectID,owner,Sysindexes,pointerstothestoragespace,tablessize,Indid,0：表定义中没有主码或唯一性约束,1：聚集索引,2：非聚集索引,Syscolumns,columnname,datatype,length,sysconstraints,基本页结构,所有页面包括页面头、页面体、页面槽,页面头,96字节,(64字节已用,32字节保留),页面体,存储数据行,8,096字节,页面槽,每行在页面内的偏,移(每行两个字节),基本页结构,：页头字段含义,Field,pageID,WhatItContains,数据库中该页的文件号和页号,nextPage,prevPage,在页链中该页的下一页的文件号和页号,在页链中该页的上一页的文件号和页号,objID,该页所属对象的ID,lsn,用于修改该页的日志序列号(LSN),slotCnt,该页上槽的总数,level,该页在索引中的级别（对于叶级别该值为0）,indexId,该页的索引ID(对于数据页该值为0),freeData,该页上第一个空闲空间的字节偏移量,pminlen,freeCnt,行的固定长部分的字节数,该页上空闲字节的数目,reservedCnt,xactreserved,由所有事务保留的字节数,由最近启动的事务保留的字节数,tornBits,flagBits,每个扇区1位，用于监测使该页分裂的写,一个两字节的位图，包含有关该页的额外信息,数据行结构,数据行结构,信息助记符大小,状态位ATagA1字节,状态位B(SQLServer,TagB1字节,2000中未使用),行定长部分的大小Fsize2字节,定长数据FdataFsize-4,列数Ncol2字节,NULL位图(每个列对应1,NullbitsCeiling(Ncol/8),位，1表示相应的列是NULL),变长列数VarCount2字节,可变列的偏移数组VarOffset2*VarCount,变长数据VarData,VarOffVarCount-(Fsize+4+,Ceiling(Ncol/8)+2*VarCount),数据行结构,位0,版本信息,作为一个3位的值对待。,0表示该行是一个基本的记录,1表示该行是一个转向记录,位1到2表示该行是一个转向存根,3,3表示该行是一个索引记录,4表示该行是一块碎片,5表示该行是一个幽灵索引记录,6表示该行是一个幽灵数据记录,位4表示是否存在NULL位图。,位5表示行中是否存在变长列,观察内部存储结构,select*fromsys.partitions,whereobject_id=object_id(Customer),-得到partition_id=72057594057457664,select*fromsys.system_internals_allocation_units,wherecontainer_id=72057594057457664,-得到root_page=0 x1A5F00000100,倒序为0 x000100005F1A，,前两个字节为文件号，后四个字节为页面号，页面是(1,23071),dbcctraceon(3604),dbccpage(adventureworks2012,1,23071,1),-输出BUFFER,PAGEHEADER,DATA,OFFSETTABLE,索引,顺序索引,基于值的顺序排序,散列索引,基于将值平均分布到若干散列桶中,索引评价指标,访问类型,访问时间,插入时间,删除时间,空间开销,B,+,树,树结点,Ki是搜索码，Pi是指针,B,+,树,每个非叶结点有n/2到n个子女,B,+,树,插入导致结点分裂,插入Clearview,B,+,树,B,+,树,删除导致结点合并,删除Downtown,B,+,树,位片索引是将属性列的域值按照某种方式进行,健康保险人寿保险意外伤亡保险,基本页结构：页头字段含义,xactreserved,RAID5包容了RAID4，同时在相同成本下，提,页面号的形式为(file#:page#)，如(3:124),插入Clearview,bulidimmediate,CurrentUseofExtent,将每个字节按比特分开，存储到多个磁盘上,列数Ncol2字节,选择合适的RAID级别,非聚簇索引的叶结点包含索引码以及到数据,记录自从上次完全数据库备份之后，哪些区间,bulidimmediate,B,+,树vs二叉树,B,+,树,胖而矮,假定树结点大小与磁盘块大小相等，为4k，,n=100，有1百万个搜索码，log,50,(1000000)4，,访问4个磁盘结点,二叉树,瘦而高,log,2,(1000000)20,T树：内存数据库,B,+,树：外存索引,B,+,树,聚簇索引叶结点是数据本身,聚簇索引的索引码是唯一的，如果聚簇索引,不是唯一性索引，SQLServer将添加在内部,生成的值以使重复的码唯一,非聚簇索引的叶结点包含索引码以及到数据,行的标识,非聚簇索引的标识可以是,RID(File#,Page#,Slot#),唯一的聚簇索引码,数据查找：,堆上的表,sysindexes,id,indid=0,FirstIAM,IAM,ExtentBitMap,1601,1681,1760,1841,Heap,Extent160,Extent168Extent176,Extent184,010101ConRuddAkhtar,0202020101Funk01WhiteFunkSmithConRudd,0303030202White02Barr01Smith01OtaFunkWhiteAkhtarSmith,04040303Durkin03.02Martin02JonesWhiteBarrFunkOta.,05Lang.03.03.SmithJones.,010101DunnRuddAkhtar,0202020101Randall01WhiteFunkSmithConRudd,0303030202Ota02Barr01Smith01OtaFunkWhiteAkhtarSmith,04040303Slichter03.02Martin02JonesWhiteBarrFunkOta.,05LaBrie.03.03.SmithJones.,010101SeattleRuddAkhtar,0202020101Paris01WhiteFunkSmithConRudd,0303030202Tokyo02Barr01Smith01OtaFunkWhiteAkhtarSmith,04040303Atlanta03.02Martin02JonesWhiteBarrFunkOta.,.03.03.SmithJones.,010101GraffRuddAkhtar,0202020101Bacon01WhiteFunkSmithConRudd,0303030202Koch02Barr01Smith01OtaFunkWhiteAkhtarSmith,040303.03.02Martin02JonesWhiteBarrFunkOta.,.03.03.SmithJones.,04.Martin.,.,04.Martin.,.,04.Martin.,.,04.Martin.,.,.,.,.,.,数据查找：,聚簇索引,sysindexes,id,indid=1,root,ClusteredIndex,Akhtar,Martin,SELECTlastname,firstname,AkhtarPage140-RootMartin,FROMmember,Ganio,WHERElastname=Ota,Smith,Page141Page145,Akhtar,Barr,Con,Funk,Funk,.,2334.,5678.,2534.,1334.,1534.,.,Ganio,Hall,Jones2434.,Jones5978.,Jones2634.,.,7678.,8078.,Martin,Martin7778.,Ota,Ota,Phua,Rudd,.,1234.,Martin7778.,Ota,Ota,Phua,Rudd,.,Smith,Smith,Smith,White,White,.,1434.,5778.,7978.,2234.,1634.,.,5878,5878,.,.,7878.,6078.,.,.,.,.,.,.,Page100Page120Page130,Page100Page120Page130,Page110,Page110,数据查找：,堆上的非聚簇索引,sysindexes,id,indid=2,root,Akhtar,Non-Leaf,Non,.,Martin,Level,clustered,Index,Page37,Page28,Akhtar,Ganio,Page12-Root,Martin,Smith,.,.,Page41Page51Page61Page71,LeafLevel,AkhtarBarr4:706:014:705:03,FunkCon4:706:024:704:01,GanioHall4:709:014:709:04,JonesJones4:708:034:709:02,Jones4:707:03,MartinMatey,Matey,4:706:044:708:01,Ota,PhuaOta4:707:024:708:02,SmithSmith4:708:044:706:03,(KeyValue),SmithWhite4:704:034:707:01,Funk4:704:02,Rudd4:705:01,White4:705:02,Heap,Page704Page705Page706,Page707,Page808Page709,01.Conn,02.,03.White,.,.,01.Rudd,02.White,03.,.,.,01.Akhtar,02.,03.Smith,04.Matey,.,01.Smith,02,02,.,03.Jones,.,.,01.Martin,02,02,.Phua,03.Jones,04.Smith,.,01.Ganio,02.Jones,03.,.,.,Funk,Funk,Ota,Barr,Hall,.,FileID#4,数据查找：,聚簇索引表上的非聚簇索引,sysindexes,id,indid=2,root,Nonclustered,Non-Leaf,Level,Indexon,FirstName,Aaron,.,Jose,Aaron,Deanna,Jose,Nina,Aaron,Adam,Amie,Con,Barr,Baldwin,DeannaDaum,Don,Doug,Jose,Judy,Mike,Lugo,Kaethler,Nash,LeafLevel,Hall,Hampton,KeyValue)(Clustered,ClusteredIndex,Barr,OnLastName,Kim,Nagata,OMelia,Barr,Cox,Daum,Adam,Arlette,Deanna,Kim,Kobara,LaBrie,Shane,Linda,Ryan,Nagata,Nash,Nixon,Susanne,Mike,Toby,散列索引,桶(bucket),存储一条或多条记录的存储单元,散列(hash),K是搜索码，B是桶地址，散列函数h(K)=B,散列函数,分布是均匀的，桶包含记录的个数是均匀的,分布是随机的，散列值不能与搜索码的值呈现出,相关性,桶溢出(bucketoverflow),桶不足(insufficientbucket)+偏斜(skew),散列索引,散列索引,溢出链,多维索引：,k-d树,树顶层结点按一维划分，下一层按另一维划分，,保持每侧各落入一半数据，直至结点数小于指,定值,多维索引：,四叉树,00011011,101111,多维索引：,R树,多维B树,区域间有重叠,位图索引,针对一些特殊的列建立索引,列中的每一个值对应一个向量中的一位,向量的长度对应与记录的条数,不适合列中值的个数太多的情况,Basetable,IndexonRegion,IndexonType,CustRegionType,RecIDAsiaEuropeAmerica,RecIDRetailDealer,C1AsiaRetail,C2EuropeDealer,C3AsiaDealer,1100110,2010201,3100301,4001410,5010501,C4AmericaRetail,C5EuropeDealer,位图索引,查询：,SelectcustFromBaseTable,WhereRegion=AsiaandType=Dealer；,10100,BitMapforRegion(Asia):,01101,BitMapforType(Dealer):,查询结果：向量与操作：,00100,位图索引,与B树的大小对比,位图索引,设表中有10M个记录，每个记录长800字节，每一页,16K字节，则扫描此表共需50万次I/O操作,“在美国加州有多少男性未申请保险？”,传统,传统,RDBMS,RDBMS,做,作,处理大量的数据,经常进行全表扫描,Gender,State,Insured,M,M,NY,CA,CT,Y,Y,N,Y,N,10M,F,ROWS,M,M-,MA,CA-,800Bytesx10MRows16K/Page,=500,000I/Os,800Bytes/Row,位图索引,对于10M个记录建立三列的位图索引共占,（10Mbit*3列/8)字节的空间，每页16K，则这些索引,仅占235页，因此存取这些索引只要235次I/O操作,GenderInsured,State,10MBits/8x316KPageCols,=235I/Os,1,2,3,4,M,M,F,M,Y,N,Y,N,CA,CA,NY,CA,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,10M,Bits,+,+,=,2,位片索引(Bit-slicedIndex),位片索引是将属性列的域值按照某种方式进行,垂直分割，然后以二进制位图的形式存储,Salesinbinaryform,Sales,Salesinbinaryform,8bit4bit2bit1bit,601100110,910011001,501010101,11,910011001,300110011,701110111,12,1011,1011,1100,1100,位片索引,datestorestateclasssales,3/132NY,3/136MAA,3/138NY,3/141CT,3/143NYA,3/146RI,3/147CT,3/149NY,A,6,selectsum(sales),fromcustomers,wherestate=NY,andclass=A,9,5,B,A11,9,B,B,A12,3,7,stateclass,=NY=A,salesinbinaryform,8421,1,0,1,0,1,0,0,1,1,1,0,1,1,0,0,1,0,1,0,1,1,0,0,1,1,0,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,1,1,1,1,1,1,0,表分区,分区视图,物化视图,按列存储,数据压缩,90,数据分区,从GB到TB到PB,电信公司的通话记录、连锁超市的销售记录,使用分区表来提高应用系统的性能,分区,将数据分散到各自的物理单元中去，以便能分别独,立处理，灵活地访问数据，提高效率,实际需要：分析往往对某种相关性的数据集合进行,某一时段的数据,某一地区的数据,某特定业务领域的数据,某一时段某特定业务领域的数据,日期往往是自然而均匀的分割,数据分区,1988分片1,1989分片4,1990分片7,健康保险人寿保险意外伤亡保险,1988分片1,1989分片4,1990分片7,分片2分片3,分片5分片6,分片8分片9,分区表,使用分区的优点,：如果表的某个分区出现故障，表在,增强可用性,其他分区的数据仍然可用,：如果表的某个分区出现故障，需要修,维护方便,复数据，只修复该分区即可,均衡I/O,：可以把不同的分区映射到磁盘以平衡I/O，,改善整个系统性能,：对分区对象的查询可以仅搜索自,改善查询性能,己关心的分区，提高检索速度,分区表：Oracle,Oracle提供三种分区方法,范围分区,根据某个属性值的范围，决定将该数据存储在哪,个分区上,散列分区,通过分区编号将数据均匀散列到I/O设备上，使得,这些分区大小一致,复合分区,先使用范围分区，然后在每个分区内再使用散列,分区,分区表：Oracle,CREATETABLEsales,(invoice_noNUMBER,.,sale_dateDATENOTNULL),(sale_date),RANGEPARTITIONBY,(,PARTITION,sales2006_q1,(TO_DATE(,VALUESLESSTHAN,TABLESPACEts_sale2006q1,2006-04-01,YYYY-MM-DD),sales2006_q4,PARTITION,VALUESLESSTHAN,(TO_DATE(,TABLESPACEts_sale2006q4),2007-01-01,YYYY-MM-DD),分区表：Oracle,createtableemp