kc第13讲-数据散列技术.ppt

第13讲: (第12章) 数据散列技术 重庆大学计算机学院 * * * * * * * * * * * * * * * * * * * * 课程名称: 数据库系统 -------------------- 第13讲：数据散列技术 项目驱动目标： 如何实现基于散列的文件组织和索引： 一、静态散列 ? 二、动态散列 ? 三、SQL中的索引定义 ? 主要讨论问题： 什么是静态散列 好的散列函数该是什么样 什么是动态散列 如何在动态散列中插入记录 如何删除动态散列中的记录 与静态散列相比,动态散列有特点 顺序索引与散列的区别 SQL中如何定义索引 Exercise 13 Static Hashing(静态散列) A bucket(桶) is a unit of storage containing one or more records (a bucket is typically a disk block). In a hash file organization(散列文件组织) we obtain the bucket of a record directly from its search-key value using a hash function(散列函数). Hash function h is a function from the set of all search-key values K to the set of all bucket addresses B. Hash function is used to locate records for access, insertion as well as deletion. Records with different search-key values may be mapped to the same bucket; thus entire bucket has to be searched sequentially to locate a record. 一 静态散列 1-1 什么是静态散列？ 问题1答案 1.1 基本概念 Example of Hash File Organization There are 10 buckets, The binary representation of the ith character is assumed to be the integer i. The hash function returns the sum of the binary representations of the characters modulo 10. E.g. h(Perryridge) = 5 h(Round Hill) = 3 h(B r igh t o n)= 3 h(Mia nu s) = 7 Hash file organization of account file, using dept_name as key 2,18,9,7,8,20,15,14 ? 字母对应的数字编号 2*317+18*316+9*315+7*314+8*313+20*312+15*311+14= 71264679513 (模10余数是3) 放入3号桶 13,9,1,14,21,19 ( ( ( (13*31+9)*31+1)*31+14)*31+21)*31+19= 380534567 (模10余数是7) 放入7号桶 1.1 基本概念 Hash Functions(散列函数) Worst hash function maps all search-key values to the same bucket; this makes access time proportional to the number of search-key values in the file. An ideal hash function is uniform(均匀的), i.e., each bucket is assigned the same number of search-key values from the set of all possible values. (桶的尺寸一样大！) An ideal hash function is random(随机的), so each bucket will have the same number of records assigned