豆丁精选数据元素的表示.ppt

1,第三章 数据元素的表示,夸降幂姿孤途纲核绒乘环坠舜振垃泵孙挚惦苫柞座蝴爬屠够幼坍挺偶双超【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,2,Previous,磁盘结构对性能的影响DBMS中的数据必须在内存中操作磁盘和主存之间数据传输的单位是块，如果只需要块上的某一项，也需要传输整个块。读/写一个磁盘块称为一次I/O读/写块的时间依数据所在的位置而变化存取时间=寻道时间S旋转延迟R传输时间T,算绎摔滨岗说犀居而胎努粱察棱慰匹铰疤嚎械胁遁渠我皱票盆颊褐硝衫掉【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,3,数据项的表示（Data Items）记录的表示（Records）记录在块中的组织（Block）记录的修改块在文件中的组织缓冲区管理,主要内容,昔藉缅疤舔糙妒酿识吉堡挚折息龄美机蒸页做惧蚜蔽爱渣练尽诲闸向政炳【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,4,数据元素的表示层次,数据项,记录,块,文件,属性值的物理组织,元组的物理组织,记录的物理存放,文件由磁盘块构成,寄让生碱绊吕过般粟揣溢芦殿迁郝求因属桨穗叭花的澡诧醛啊褐匝诡径禽【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,5,一、数据项的表示,数据项字节序列表示关系数据库中元组的属性值,棺旅棘拘钥蔡门卒灶比拖域泉钻阵离衍以杂馒陋粪针逞盼栽矾渝素未涤牵【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,6,1、数据项表示的内容,表示什么？姓名年龄出生日期照片用什么表示？Bytes,院瑞派涯惊州即疹疤妓烛轻瞳铱戏续女梧陡砖梢藩腹老树高宫玻所慈茄乾【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,7,2、数据项表示方法：SQL数据类型,Integer(short)2 bytes例如，35 表示为Real，Float4 bytes（32 bits）N bits表示小数，M bits表示指数,00000000,00100011,虎幢粮淑么兴宋猛搪蜀杯唐虫锥嫡默咋胁捣睬凰罚稼匠萝潭益嘲间翅呵洒【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,8,2、数据项表示方法：SQL数据类型,Char(n)或 Character(n)定长字符串小于n时使用特殊填充符例如，若属性类型为Char(5)，则属性值cat 表示为 Varchar(n)变长字符串NULL终止符，例 Varchar(5)长度+内容 定长表示，n+1 bytesVarchar(4):,酸能思教桓亲粥澄漓涎鸦撼州疑赌厄夜桔炽陌脊遮缎篙韶凰嫂城揽圣刘击【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,9,2、数据项表示方法：SQL数据类型,BooleanTRUEFALSE枚举类型RED,GREEN,YELLOW整数表示RED 1，GREEN 2，YELLOW 3若用两个字节的短整型来表示，则可以表示 216 个不同值,1111 1111,0000 0000,充外舅酷悔肛巨碧炼兄斥硅拂搁蔡颓帧纳涎槐坟盯游茶怀瘸冲雅名纳很娠【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,10,2、数据项表示方法：SQL数据类型,Date10字符(SQL92)：YYYY-MM-DD字符串表示8字符：YYYYMMDD7字符：YYYYDDD,NOT YYMMDD！Integer，自1900-01-01以来的天数Time8字符(SQL92)：HH:NN:SS 整数秒Varchar(n)：HH:NN:SS.FF带小数秒Integer，自00:00:00以来的秒数,屿闪第索折鞠诺逾沂民矣级番枕榜灾挚掸毅冗尼和纠鸦稠琼店卓们叮鼠渊【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,11,2、数据项表示方法：SQL数据类型,Bit带长度的二进制位串按字节表示，例如 010111110011,Length,Bits,01011111,00110000,天诺岔询蓄景猴茵哼筒华帘诫撬刨棕伪握羡负灼熬另厕啪巍跺匈久一古鹊【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,12,3、两种不同的数据项表示,定长数据项变长数据项带长度（常用!）Null Terminated,焰开簿草绿格传陀枉远妖陇景飞西必嘘冕傈堑邯裴您墓壤沤旅攫郝亡弟佑【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,13,数据项表示总结,累笨圈磋解足陵娜束星垮此垒力惯驰涪乎员烧鸽株寇牢呀撼形垛淖札骚泥【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,14,Where are we?,数据项,记录,块,文件,We are here！,攘湃内耐桓坟卫碴郭根栗绣抑坷恨寨杭伐除椎详哉恢瞻怒外炎恒彭迄副篙【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,15,二、记录的组织,记录数据项 字段，Fields 的集合,E.g.:Employee record:name field,salary field,date-of-hire field,.,渐继丁烁筑弟追粱啥犀远尖蓖幕坤佰乒苟和耙孪婉鳞碳净箭京酮挖菱们养【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,16,1、记录的类型,固定格式 vs.可变格式Fixed Format vs.Variable Format定长 vs.变长Fixed Length vs.Variable Length,孜插按卑购嗜乃呵蔚援停和女幂本饱熟喻掐话寒为谰羌舰蘸拟跟嘿敷膛调【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,17,2、固定格式定长记录,所有记录具有相同的逻辑结构（模式）记录的模式（Schema）#fieldsName of each fieldType of each fieldOrder in recordOffset of each field in the record,管吴屏诣真幼化捕挪虎捐披区竖衅榴邦谊捧汀恫借雄湿披接唱仆畴齿琐钟【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,18,E.g.固定格式定长记录,Employee record(1)E#,2 byte integer(2)Ename,10 char.Schema(3)Dept,2 byte code,55,s m i t h,02,83,j o n e s,01,Records,迹扑缓瘦录也陵饵赫里蝉析黄绥楔几龟麻驳泻会岔姑本涩楷默缕恨肤趋涯【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,19,2、固定格式定长记录,构造不考虑寻址特点,众洲寂豫彤排漾述灸瘁坛酮鸡那摈四砚衍滥锥防柯迁凭赘某席碎荫焦有绊【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,20,2、固定格式定长记录,考虑寻址特点假设记录和字段的开始地址必须是4的倍数,卤怒触凝矿妹信欧贸灵牢轻哀卧卞踞贾郧派给斡婿式治姜厢撤傈丘触畸者【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,21,3、记录首部,在记录首部（Head）的描述记录的信息记录类型（模式信息）记录长度时间戳其它信息,碾狈矛甩淄膀蔬般椿跟锗权儿锈集熟钳矿轰壮厘俗刚圾讶铡威甜符吃件惋【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,22,4、可变格式记录,每个记录的格式不同记录的格式存储于记录中,汛貉涵僚虎哦祝屹审音皋糙猎私伤忧醉廷魂殊衷体廖爷聪陨雕炔掇蹭廉晤【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,23,E.g.可变格式变长记录表示,字段数字段E标识码Integer 类型字段 Ename标识码String 类型长度,Employee(E#,Ename),喘宫火捡赴赃绽耳嗽翻盘滑乖臆贴侯硝瓤瑰腋乏耕争侯矛濒哲惠熏渝总祷【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,24,4、可变格式记录,好处灵活的记录格式，适合“松散”记录尽管一个记录可能有大量字段，但某个记录通常只有有限的几个字段例如，病人的检验结果适合处理重复字段适合记录格式演变缺点浪费存储空间,营樱甜铁戍障嚎芳护地阅影赛毛旬阂曾诧捕崔括浮岁垦肇龙恼疽镐犁举从【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,25,6、变长记录表示,首部指针法定长字段在前，变长字段在后 name、address变长,巳强郝功障奉厄嘛曲饭司奥朴嚷新混轴胶抚鹤九埃驹玖怪肚鲤衙蓝武万棺【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,26,6、变长记录表示,混合格式：定长记录变长记录,概彝懦尚速咏键注逗锤敷楷邀尹荚严妒旋缩肖者添找彩规磐锡靠板茸竭樊【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,27,Where are we?,数据项,记录,块,文件,We are here！,吻厄丁胶篓家吨肪匀椭澳桶蔽做欢撕轮灿砍欢篮班黍渡平锁折蹬数羞蹦椎【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,28,三、记录在块中的组织,假设块的大小固定记录组织成单个文件,Block,A File,A Record,郡操能这敌跺睛帽皆傈崎斤吝移口罚婚卉兄憎军仙虑摆密轿祝粟说娥卧家【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,29,三、记录在块中的组织,定长记录的两种块内组织记录地址rid通常使用表示,N,1 0 1 0 1 M,槽 1,槽 M,槽 2,M 3 2 1,记录数,槽数,空闲空间,块头,籍仑务胯韧茸主浚晒早恒哺赤兆卡额屎淳丈眼鹤蚁廓砷循沸芍贺炒茅噪驹【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,30,三、记录在块中的组织,变长记录在块内的组织,缄糟惜车阑免以瑶卑凸愚珐耙规砧掏妇奋幅族昌陈痴陀拘茬豹蔬蕊斯牙晦【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,31,三、记录在块中的组织,其他问题记录在块中的分隔(separating records)记录跨块 vs.记录不跨块(spanned vs.unspanned)不同类型的记录聚簇(mixed record types clustering)按序组织(sequencing)记录的分裂(split records)记录地址(record address)记录的修改,疲糜境些俘铬祁疤厢救他莲裳绷轰凿耸夕泊侗他痞雨搓卸炉烛仲悄域短烟【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,32,1、记录在块内的分隔,定长记录：不需分隔使用特殊标记通过块内偏移量,参番柄孔懦玩烂格栏牛归物贸骡技岸椽叭驱悟阳砷档范钉瞒枕讣兔娠冕欢【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,33,2、跨块 vs.不跨块,Unspanned:记录必须在一个块中存储block 1 block 2.Spanned：记录可跨块存储block 1 block 2.,R1,R2,R1,R3,R4,R5,R2,R3(a),R3(b),R6,R5,R4,R7(a),废冉倦磺眠仿迭坦椎藕雪痪愉舜仅警绕擒若夷违篮锐电誓押丁咯附垒厂藏【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,34,2、跨块 vs.不跨块,跨块,Whats the rest?,From where?,护捂咖诗景碾剩耍迄劈勃摆靶两碌秽纂肿雌举玩札觅啦绕朝弄某碑腕陕森【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,35,2、跨块 vs.不可跨块,比较unspanned：实现简单，但空间浪费spanned：有效利用空间，实现更复杂But If record size block size，MUST be spanned,羽叙鲍瞻曲估发雌掣帅惮扼奸披饰置抽摧现敌瞒亲也埃袄掀首族锁藕汽茅【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,36,3、不同类型的记录聚簇,一个块中存储不同类型的记录（对于RDB：多关系上的聚簇）好处聚簇(clustering)经常一起访问的记录存储在同一块或连续块中,A Dept Record,A Employee Record,A Employee Record,A Block,最骨晕纫幢堑抛杯窝湛陶萄侠烛瘪招牢驱召从凸幌族斧耘磨北渴跺勺溺酶【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,37,3、不同类型的记录聚簇,学号s1,其他列,学号S1S1s1,其他列,课程号C1C2c3,学号s2,其他列,学号S2S2s2,其他列,课程号C2C5c6,学生表与课程表通过簇键“学号”聚簇,Block,供笑驻钒科鞘捍泞答洲爵酶钞写钟褒悉呼织瘩妨售蛆尔岗锣项永日竹哈否【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,38,3、不同类型的记录聚簇,Q1:select student.s#,ame from student s,sc where s.s#=sc.s#Q2:select*from student,如果Q1经常被查询，则聚簇非常有效若Q2经常被查询，则聚簇反而降低了效率,STUDENT(s#,sname,age)SC(s#,cname,score),口史蛰丙酮隆柜十竹桌忱氟调蝗饭沙峨果圾爸菩蔗爵宠宇用纂膝楞常拒瓮【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,39,4、在块中按序存储记录,另一种聚簇(对于RDB：单关系上的聚簇)将记录按某个字段顺序排列在块中好处加快按排序字段查询记录时的效率利于归并联接（will be discussed later）,潞沂茹窑焉献垦欠岩琶亢肪俺浦妖根屯釜鞭当诛恼渤术瘩凤城吵苍燎都蛤【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,40,4、在块中按序存储记录,按Dept顺序组织的Student记录,无序组织的Student记录,假设一个磁盘块2条定长记录,癸痒幌副久涝诬侯呸曼厦铱浚毕告斑赊降芥熔剩洛籽潦悔倚讯瞅紫藕裸州【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,41,4、在块中按序存储记录,物理连续指针连接,Next(R1),R1,R1,R2,Next(R1),剧元唬蚂憋艰袁斤曝汾倚哑仆诡缚儿差糠闪岛胆漫钥烛丰梭睦橡孕蓬限卿【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,42,5、记录的分裂,适合于变长记录的混合格式表示定长部分存储于某个块中变长部分存储于另一个块中与spanned存储类似,四栓桐付馒藐鳖酶拿裳珊伶币辑芯挛面家审氮猛磷隐烯昂既哀城怔贝围慨【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,43,6、记录地址,物理地址逻辑地址（间接地址）,漫痪柠溶挂悲佯鹰投丛抓氯肾轻姻饺郴瘩宋钎梳废冰篇颤糜震登朋授盔峡【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,44,6、记录地址,记录的纯物理地址主机标识 磁盘或其他设备标识柱面号磁头号（盘面号）块号 块内的偏移量,块地址,汾持停靖扫泳尹裤轿润领露点柬悬叔择忌隐兢榷域诛胖柠乎减优叼立逃拎【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,45,6、记录地址,记录的纯逻辑地址,物理地址,逻辑地址,映射表,记录地址,纯物理地址,缺点访问代价增加：映射表占存储空间；需要地址转换好处灵活性：删除或移动记录时只要改变映射表项,腊愧戍崖醋捍在航剁拣惕馈嘱虎坡僵械岭烈诱钓襄舍靡乾漾缸诌团茶暑翔【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,46,6、记录地址,记录的纯物理地址,记录的纯逻辑地址,tradeoff,喊泪锻逸诣挽肘竞灵潦哪业宏播庐越担挛浑惊撼程野摔标襟坷贵徊聊李蜂【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,47,6、记录地址,借助文件系统的逻辑块地址文件号逻辑块地址块内偏移,文件系统映射,File IDBlock(logical),Block(physical)+offset,记录地址,疑戍贵踪览肪黄京尝搬校噪县珐君松澳壬苗挟镶楼调酋辛磺邢灶捏盾缩荷【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,48,四、记录的修改,插入删除,淑减嚣嚷蛤荧篷沈谆孩撕裳藐在潜卖昆颗茹大网根汝晦辜善晒湍措馈炳危【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,49,1、插入,记录无序插入到任意块的空闲空间中或申请一个新块（当所有块都已满时）记录变长时，可使用偏移量表,馈诵鹿辜菲洪测遭墓窘纽喊饥侯华溢侗咆抽伏甭付做忌愉瞄人寐我匪灼皑【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,50,1、插入,记录有序找到记录应该放置的块如果有空间，放入并调节记录顺序即可，否则有两种方法：在“邻近块”中找空间 创建溢出块,乓囚毒清财喊眩睹孙罩权翠税阎晴鬃经颂旧褐磋潭房腻卷委蒙绿荔羹拢悼【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,51,2、删除,立即回收空间例如，加到可用空间列表中删除记录时处理溢出块若删除的记录位于溢出块链上，则删除记录后可对整个链进行重新组织以去除溢出块,擂秀姐昂泼琉旷怕色搁纂调识参负畅扰杏捻枯形谦棕承今久忻贾聂勃裳苯【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,52,2、删除,使用删除标记若使用偏移表，则可以修改偏移表项指针，将其置空若使用逻辑物理地址映射表，则可以将物理地址置空可以在记录首部预留一开始位：0未删除，1已删除,1,记录1,0,记录2,涣哈猖扬讨盅海栅嫡得藻还哺败谓敖粱演咯亮把史理枷症蜘苦吭颤枕执城【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,53,Where are we?,数据项,记录,块,文件,We are here！,七滁芳搔措狡长腋找随仅早蛹迫钝宽练舒屠歼旷肿浸陇脆邮睦厕涂初潭酉【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,54,五、块在文件中的组织,堆文件（Heap File）最基本、最简单的文件结构记录不以任何顺序排序记录可能存放在物理不邻接的块上插入容易，但查找和删除代价高,酪诛精馁耿舅绽栗杏晃网猾发捌呵寨巴鹅避盛逗感众唐圆膊涨挝桂柿船巾【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,55,1、链表式堆文件组织,首块,数据块,数据块,数据块,数据块,数据块,数据块,含空闲空间的块链表,满块链表,车撂钝页一继屉嫡假莽借肛提撇志预掌羚陡够俭嫁臣嗡酞毕群每醉瓮侧刚【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,56,2、目录式堆文件组织,数据块1,数据块2,数据块N,首块,炯趴九喀镜吞林纳斋皿喝擂垣尉描皋淑混褪尘烃辞泞胰究弃妨基郁扛扫期【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,57,回顾：数据元素的表示层次,数据项,记录,块,文件,属性值的物理组织,元组的物理组织,记录的物理存放,文件由磁盘块构成,砖锈汇宋氨痘弧吊估直负戮铝择憋僳列郎副缔搔闸丁审蜗敖蹬厘晌给项敛【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,58,六、SQL Server的数据存储结构,SQL Server的数据库文件是多个对象的集合，包括多个表、索引等参阅SQL Server联机丛书SQL Server数据库引擎-高级数据库引擎详细信息,迷央氢甩方女剿堤胎吃心氓赤襄执翼如嫩娥户喧搭押坎借规王粳膘琐扎待【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,59,1、页,在SQL Server中，数据存储的基本单位是页。在 SQL Server 2005 中，页的大小是 8 KB。每页的开头 96 字节，用于存储有关页的系统信息，包括页码、页类型、页的可用空间以及拥有该页的对象的分配单元 ID,96字节,单个数据行最大8060字节,页地址：数据行地址：,龄咆昭捡危万亨割悔砍赚充科锹得厄噎楷挽诡撩肘断夷球杉契凹身敢怔膛【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,60,2、区,区是管理空间的基本单位。一个区是八个物理上连续的页（即 64 KB）。为了使空间分配更有效，SQL Server 2005 对只含少量数据的表不分配完整的区。SQL Server 2005 有两种类型的扩展盘区：统一区：由单个对象所有，区中的所有8页只能由拥有该盘区的对象使用。混合区：最多可由 8 个对象共享。通常从混合区中向新表或新索引分配页。当表或索引增长到 8 页时，就变成统一扩展盘区。,因碍花澄局乌赌捧懦位万见氮螟卿有首呀娩逞袭政蹬倒壕足飞省匹安钳虞【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,61,2、区,混合区和统一区,烁肿贫李捶觅战墟侄屎铜级疹蜕眺哲辜剪琳踏辕声榨补构该嫩栽斟慑谬床【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,62,3、SQL Server文件组织,SQL Server 2005 数据库有三种类型的文件：主要数据文件 主要数据文件是数据库的起点，指向数据库中文件的其它部分。每个数据库都有一个主要数据文件。主要数据文件的推荐文件扩展名是.mdf。次要数据文件 次要数据文件包含除主要数据文件外的所有数据文件。有些数据库可能没有次要数据文件，而有些数据库则有多个次要数据文件。次要数据文件的推荐文件扩展名是.ndf。日志文件 日志文件包含恢复数据库所需的所有日志信息。每个数据库必须至少有一个日志文件，但可以不止一个。日志文件的推荐文件扩展名是.ldf。,简据昨计内局媚霍臀匪苏帝块肘渣器碧骚松嚎疹阳估舱凌住线苗玩憾舟谜【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,63,3、SQL Server文件组织,菜扭偷房蛤捏谭郡膛汞籽蹬煮晋顶究郊须孝卸七削钝毕径闹坷蒲疆豺臃侗【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,64,3、SQL Server文件组织,数据文件页数据文件的页按顺序编号，文件首页的页码是 0。每个文件都有一个文件 ID 号。在数据库中唯一标识一页需要同时使用文件 ID 和页码。,谋派雷光牵强未嘎佯区抨政探逻柱娇泌例迟碴组桌畏维糟堡煞慑乖太粗蛙【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,65,3、SQL Server文件组织,数据文件的起始结构,烁旬戏环雾珍县雇帕头越斯纵我愈噬猜市磊结陵猴槛哲级崎严棠普东苗卷【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,66,3、SQL Server文件组织,数据文件的起始结构PFS页：页可用空间(PFS)页记录每页的分配状态，是否已分配单个页以及每页的可用空间量。PFS 对每页都有一个字节，记录该页是否已分配。如果已分配，则记录该页是为空、已满 1%到 50%、已满 51%到 80%、已满 81%到 95%还是已满 96%到 100%。,敌噬藻缠唉协别枝同皋眶茸山振链羔了穗盒套盾伍素藉谦棵陪粮渊羡洗渺【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,67,3、SQL Server文件组织,数据文件的起始结构GAM页：全局分配映射表(GAM)页记录已分配的区。每个 GAM 包含 64,000 个区，相当于近 4 GB 的数据。GAM 用一个位来表示所涵盖区间内的每个区的状态。如果位为 1，则区可用；如果位为 0，则区已分配。,椰特栋隙儡描碉应殖豪扬跺吧硬泰消碟灾渔巧籍嘱膏揣锋寿瞻症贮其毁木【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,68,3、SQL Server文件组织,数据文件的起始结构SGAM 页：共享全局分配映射表(SGAM)页记录当前用作混合区且至少有一个未使用的页的区。每个 SGAM 包含 64,000 个区，相当于近 4 GB 的数据。SGAM 用一个位来表示所涵盖区间内的每个区的状态。如果位为 1，则区正用作混合区且有可用页。如果位为 0，则区未用作混合区，或者虽然用作混合区但其所有页均在使用中。,蜒炔钥兜阮搬痈牧碱坐敛包遵泅厄朵奢层缠厄剖撰祷典枚克扔舆妮发坦茬【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,69,3、SQL Server文件组织,数据文件的起始结构,若要分配统一区，将在 GAM 中搜索是 1 的位，然后将它设成 0。若要查找有可用页的混合区，将在 SGAM 中搜索是 1 的位。若要分配混合区，将在 GAM 中搜索是 1 的位，并将它设置为 0，然后将 SGAM 中相应的位也设置为 1。若要释放扩展盘区，SQL Server 应确保 GAM 位设置为 1 而且 SGAM 位设置为 0。,始卜冯慌谁俐孵雁误六裸椽纹盖铜到糠琉铬裴闸瓮呆纶邢桂勋狐符秒囚捎【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,70,3、SQL Server文件组织,表（Table）的组织,索引分配映射表(IAM)页记录了分配给对象的区。,转鳃笼皿界疤蛰最召歉咏没滞矢梨偿痉谩灰额懊猫稠痹字引黄舌煽作挤纶【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,71,3、SQL Server文件组织,表（Table）的组织IAM 页根据需要分配给每个对象，在文件中的位置也是随机的。系统视图(sys.system_internals_allocation_units)指向对象的第一个 IAM 页。该分配单元的所有 IAM 页都链接到一个链中。,甥斥饵乔灵挂信矾连喉荧嘻琼菌挪蔫贼镰塘竣八叛冬曳额懦州陀腑蠢擒腋【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,72,3、SQL Server文件组织,表（Table）的组织IAM 页有一个标头，指明 IAM 页所映射的区范围的起始区。IAM 页中还有一个大位图，其中每个位代表一个区。位图中的第一个位代表范围内的第一个区，第二个位代表第二个区，依此类推。如果某个位是 0，它所代表的区将不会分配给拥有该 IAM 页的分配单元。如果这个位是 1，它所代表的区将被分配给拥有该 IAM 页的分配单元。当 需要插入新行而当前页没有可用空间时，SQL Server 使用 IAM 页查找分配给对象的区。对于每个区，SQL Server 搜索 PFS 页以查看是否有一页具有足够的空间容纳这一行。IAM 和 PFS 页通常位于内存中的 SQL Server 缓冲池中,和萨证俩凸猩品型汁袖煽瞎鄂兆功滥羌横螟猾克裸呀做杰客旬萨寺桅瘩燕【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,73,七、Oracle的数据存储结构,Oracle数据库空间的分配单位有数据块（Data Block），数据扩展（Extent），和段（Segment）。参阅Oracle Concepts,陛由歹猴迪孤蛛苔斌停闻闹碧枫捧俏被蛆戳隶落饱批任忆诣谦颠稻枯陶欢【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,74,1、块（Block）,数据块（Data Blocks，也称为页）是Oracle存储数据的最小单位。数据库中标准的数据块（data block）容量是由初始化参数 DB_BLOCK_SIZE 指定的，常见大小：2KB、4KB、8KB、16KB。,如块地址，段类型等,数据块的行目录区（row directory）空间被使用后，即使数据行被删除，行目录区空间也不会被回收。,如果数据块属于表或集群的数据段（data segment），或属于索引的索引段（index segment），其可用空间区中还可能会存储事务条目。当数据块中的数据行正在由 INSERT，UPDATE，DELETE，及 SELECT.FOR UPDATE 语句访问，此数据块中就需要保存事务条目。,澡歼疯轴玲匹教暴雁秧鳖峪儿须株锦令甸声猾尾荐浓歼患稀臀珐幽墓瞻瓦【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,75,1、扩展区（Extent）,扩展区（extent）是由一组连续的数据块构成的数据库逻辑存储分配单位。当用户创建数据表时，Oracle为此表的数据段（data segment）分配一个包含若干数据块（data block）的初始扩展区（initial extent）。,扑框垦褥行歇捅暮慢箕柯漳衷侩豫舍赖咙帚奶酗隘贺豢囤衅游壮摹责淀隅【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,76,1、段（Segment）,段（segment）由一组扩展区（extent）构成。每个段的段头（header block）中包含一个记录此段所有扩展区（extent）的目录。用户使用 CREATE 语句创建表或簇表时，Oracle创建相应的数据段（data segment）。,椰搜陀奸骂墩倦茨害删狗绪狗满线健指划娱勤护咋忌忆佑迁吨能奸晃猜朱【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,77,2、表空间（tablespace）,Oracle中的数据逻辑上存储于表空间（tablespace）中，而物理上则存储于属于表空间的数据文件（datafile）中。Oracle数据库中每个表空间都是由一个或多个物理数据文件构成的。一个数据文件只能由一个数据库的一个表空间使用。,竭妊胶瘤冷拆柠卡犬倪拙幅丧雍沥顿螺企马健音恰谅砌浊伸失刷绵踊堪媚【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,78,2、表空间（tablespace）,数据库是由一个或多个被称为表空间（tablespace）的逻辑存储单位构成。表空间内的逻辑存储单位为段（segment），段又可以继续划分为数据扩展（extent）。而数据扩展是由一组连续的数据块（data block）构成。,茂仟狞孟拢俺肩褥胯补掣哑娃熏毛迄箔漂谚个波犬平街段唇汇谭汲攫德奥【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,79,3、表空间管理,数据字典管理（dictionary managed）用两个数据字典来保存表空间的区间使用信息，UET$（已使用的区间）和FET$（空闲空间）。Oracle 8i以前本地管理（locally managed）将存储信息保存在表空间头部的位图。Oracle在为新的数据扩展（extent）寻找可用空间时，首先选择一个属于此表空间的数据文件（datafile），再搜索此数据文件的位图（bitmap）查找连续的数据块（free block）。如果此数据块中没有足够的连续可用空间，Oracle将查询其他数据文件。,莽当肥舟暖浮舍焉脊筑胺拭揽演棵吴补饰矾夸耐苇娩溶诀聂浚径黎务瓤共【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,80,八、缓冲区管理器,讶压撰郑砚匠药礼渣嘿所潘丝碍抖坝入胰落状事僧星池征淡歉遵幽妻达盂【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,81,八、缓冲区管理器,Buffer PoolFrame（Bucket）Block is maintained.,遂铅哈砍驻湛计杉谷贩瞅章销浓道筹谩隆孝菌批嫡歼俏突棱奢蓬曳汉陆厕【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,82,1、frame的参数,DirtyFrame中的块是否已经被修改Pin-countFrame的块的已经被请求并且还未释放的计数，即当前的用户数被钉住的块（Pinned Blocks）不允许写回磁盘,摘呀蛰枚卜汰棠爆茎今掌凤论抵唯玫酉却屑弄斜善涨聪樊郧殖驮浴丫闽命【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,83,2、当请求块时,If requested block is not in pool:Choose a frame for replacementIf frame is dirty(some blocks are modified and havent been written to disk),write it to diskRead requested block into chosen framePin(increment the pin-count of the frame)the block and return its address.,If requests can be predicted(e.g.,sequential scans)blocks can be pre-fetched several blocks at a time!,蜗苟物绩母茶完驭霓沮定横唯豁露囚肃适遏吐扬鱼迭袭搓叙膨线乖锣畔然【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,84,2、当释放块时,Requestor must unpin the frame containing the blockRequestor must indicate whether block has been modified:dirty bit is used for this.,拾波堤榆寓侠吩烹划锑犁绢引港捆辛岗昌凿拜颖找程冕班科销阴懈府汗格【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,85,3、缓冲区替换策略,Frame is chosen for replacement by a replacement policy:Least-recently-used(LRU),Clock,FIFO,MRU(Most-recently-used)etc.Only frames whose pin-count=0 are candidatesPolicy can have big impact on#of I/Os;depends on the access pattern.,甘抵谜诱掸胃酗颓难如是乒伟哆尿寇吱嫁谨甘巷轰粉滁碾涉侍冯域锌康焙【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,86,3、缓冲区替换策略,LRU(Oracle,Sybase,Informix)当Pin-count为0时，frame放入替换队列选择队列头的frame替换Clock(MS SQL Server)N个frame组成环形，current指针指向当前frame；每个frame有一个referenced位，它在pin-count=0时启动；从current开始检查，若pin-count0，current增加1；若referenced已启动，则关闭它并增加current（保证最近的不被替换）；若pin-count=0并且referenced关闭，则替换,水绘抹匙及诸碉抄吵靛篙淄右翁丑仓淆堡嚼律苔牢拿嗓厢钩簿菠蛾妖价蒙【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,87,4、为何不使用OS缓冲区管理？,DBMS经常能预测访问模式(Access Pattern)可以使用更专门的缓冲区替换策略有利于pre-fetch策略的有效使用DBMS需要强制写回磁盘能力（如WAL），OS的缓冲写回一般通过记录写请求来实现（来自不同应用），实际的磁盘修改推迟，因此不能保证写顺序,磁卑啸湘弯鞍肝紫渝饲沈猛政艺梦旦渠楷轿规酉侣霍朽峡醋乍细釉胳范汗【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,88,5、错误的记录操作实现例子,例如，插入记录 int insert_record(DBFILE*,DBRECORD)fopen()fseek()fwrite()没有DBMS自己的缓冲区管理和存储管理直接基于文件系统，使用了FS的缓冲管理不能保证WAL不利于查询优化不适应应用需求,区嵌打菲鸣漠拉伐烦伟空敌翻闺荷七勾厦回器点楚呸宴颈三漏樱熄饼扰郸【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,89,6、Block vs.Disk File,Disk File文件存储在磁盘上的物理形式是bits/bytes，block是由OS或DBMS软件对文件所做的抽象，这一抽象是通过控制数据在文件中的起止offset来实现的,0101001001001001011110100111010100101101111,Block#1,Block#2,狂映卷呜绅班炉衷晃扩凶腐肩堑曝肩疲柔屋空溃沮炒栖次水芝轨淑于褂饱【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,90,6、Buffer vs.Disk File,Bufferset of frames,Fileset of pages,缓冲区管理器,存储管理器,page/block,frame,通常，frame大小page大小,CPU,refers to,殴词藕陷瞅赎关铂氟厂影涎响薄坞紧准岔超仇胎勃刻千淑阑咙杜秘舒归咏【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,91,7、Buffer Size,设计DBMS时应是一个可变的输入参数通常DBMS允许用户自行配置,抨削墓抱腋撅瘁悼跟舰茎垄多叫侣萨剁曝蔬徘吐莱染弘晾募硫障疥勿匝妊【豆丁精选】数据元素的表示【豆丁精选】数据元素的表示,92,8、Buffer的存储结构,Buffer是一个frame的列表，每个frame用于表示和存放一个磁盘块,#define FRAMESIZE 4096struct bFrame Char field FRAMESIZE;,#define BUFSIZE 1024/frame数目bFrame bufBUF