数据库系统概念12-索引与散列(1)

1、数据统系统2022-6-31/131Book :数据库概念数据库概念 Ver.5 by Silberschatz 等等Chapter 12 : Indexing and Hashing第第12章章 索引与散列索引与散列1数据统系统2022-6-32/131项目驱动目标：项目驱动目标：如何快速存取数据库中的数据：如何快速存取数据库中的数据：一、顺序索引一、顺序索引二、二、B+B+树树 主要讨论问题：主要讨论问题：什么是顺序索引，有何用途什么是顺序索引，有何用途 什么是稠密与稀疏索引什么是稠密与稀疏索引什么是多级索引什么是多级索引, ,有何用途有何用途顺序索引如何更新顺序索引如何更新何时需要建立辅

2、助索引何时需要建立辅助索引什么是什么是B+B+树索引树索引B+B+树有何特点树有何特点B+B+树索引如何用于查询树索引如何用于查询1.1.B+B+树索引如何更新树索引如何更新 数据统系统2022-6-33/131Basic Concepts 基本概念Ordered Indices 顺序索引 B+-Tree Index Files B-树索引B-Tree Index Files B-树文件Static Hashing 静态散列Dynamic Hashing 动态散列Comparison of Ordered Indexing and Hashing 比较Index Definition in S

3、QL SQL 中的索引数据统系统2022-6-34/131l“检”与“索（办手续）”。在图书馆借书时，l关键字到记录位置的对查表,即下列三元组的集合: l索引项 (关键字，记录地址，附加信息)， ll例 以年龄为关键字，定义Hash(Age) = Age Mod 12，把人按年龄分成12个组，即 通常的12属相“鼠、牛、虎、兔，.”。 在同一属相中再线性搜索，寻址效率提高 12倍。 找书的时间比办理找书的时间比办理手续的时间长得多手续的时间长得多数据统系统2022-6-35/131“检”与“索（办手续）”。在图书馆借书时，关键字到记录位置的对查表,即下列三元组的集合: 索引项 (关键字，记录地

4、址，附加信息)， 例1 以年龄为关键字， 定义 Hash(Age) = Age Mod 12， 把人按年龄分成12个组，即 通常的12属相“鼠、牛、虎、兔，.”。 在同一属相中再线性搜索，寻址效率提高 12倍。 数据统系统2022-6-36/131例2 影剧场分单双号进门，相当于Hash（N ）= N Mod 2，使观众入座速度提高一倍。 例3 在英文字典每个字母开始处贴一标签，相当于定 Hash（WordStr） WordStr0， 提高了查字典的效率例4 宝光寺：数罗汉, 领取所谓命运卡. Hash(Person)=(RedomSeed+Age+1)*2+SexSex is 0 or 1数

5、据统系统2022-6-37/1312. 无序索引 索引映射 IndexMap：关键字 - 记录号 ，而索引文件不排序。平均搜索次 数为关键字总数/2 ，由于索引文件比主文件小（通常小一个数量级， 可以全部或大部分 读入内存，在内存中搜索定位，从而提高了速度。可以比喻为小无序管大有序。 例 一本书的目录可看成是无序索引映射 IndexMap : 章节名称集合 页码集合。 由于目录相对较小，易于一目十行地浏览，加快了检索内容的速度。 数据统系统2022-6-38/1312. 无序索引 索引映射 IndexMap：关键字 - 记录号 ，而索引文件不排序。平均搜索次 数为关键字总数/2 ，由于索引文件

6、比主文件小（通常小一个数量级， 可以全部或大部分 读入内存，在内存中搜索定位，从而提高了速度。可以比喻为小无序管大有序。 例 一本书的目录书的目录可看成是无序索引映射 IndexMap : 章节名称集合 页码集合。 。 由于目录相对较小，由于目录相对较小，易于一目十行地易于一目十行地浏览浏览，加快了检索内容的速度，加快了检索内容的速度数据统系统2022-6-39/1313. 顺序索引（Sequential Index) 在无序索引的基础上作如下改进：将索引文件排序后保存，因而在索引文件中搜索关键字可以用二分法，计算复杂度为 Log2（N ），当N 30 时，就有显著效益。顺序索引 又分为两类：

7、 “小有序管大有序” 和 “小有序管大无序”。 数据统系统2022-6-310/1314.稀索引 是小有序管大有序的改进型。既然索引文件和主文件都是排序的。那么，隔 N抽 一而建立起来的索引集合就缩小到原来的 1/N，其定位误差小于N ，然后在N 个项中线性搜索。 例 英汉字典中的眉索引，再每页顶上列出当页的始词和尾词，组成了高效的，节省空间的稀索引。 数据统系统2022-6-311/131例 在1971年版的新华字典中查“飞”字，利用了“ 部首检字”和“检字表”两级 索引，因而能在正文中迅速查出释义，如图5.1所示。 部首检字 - 检字表第15页 - 正文111页 乙 15fei飞：111一

8、划 部首检字 检字表第15页 正文111页 密索引飞：鸟在空中的运动-稀索引（书眉）数据统系统2022-6-312/131Indexing mechanisms used to speed up access to desired data. l E.g., author catalog in librarySearch Key - attribute to set of attributes used to look up records in a file.index filefile of index entries (search-key, pointer)Index files sm

9、aller than the original file （以小引大）Two basic kinds of indices:l Ordered indices: 顺序索引顺序索引l Hash indices: 散列索引 keys 分散散 列列入 “buckets”数据统系统2022-6-313/131Access types supported efficiently. E.g., 有效支持类型l records with a specified value in the attributel or records with an attribute value falling in a sp

10、ecified range of values.Access time 查 时间 Insertion time 插 时间Deletion time 删改 时间Space overhead 空间数据统系统2022-6-314/131Basic Concepts 基本概念Ordered Indices 顺序索引B+-Tree Index Files B-树索引B-Tree Index Files B-树文件Static Hashing 静态散列Dynamic Hashing 动态散列Comparison of Ordered Indexing and Hashing 比较Index Definit

11、ion in SQL SQL 中的索引Multiple-Key Access 多关键字存取数据统系统2022-6-315/131In an ordered index, index entries are stored sorted on the search key value. E.g., author catalog in library. 1表可以有多个！Primary index(主索引主索引/聚集索引聚集索引): in a sequentially ordered file, the index whose search key specifies the sequential o

12、rder of the file. 使使文件记录同其序Also called 聚集clustering index 1表仅能有1个！The search key of a primary index is usually (but not necessarily) the primary key.Secondary index(辅助索引辅助索引/非聚集索引非聚集索引): an index whose search key specifies an order different from the sequential order of the file. Also called non-clu

13、stering index.Index-sequential file(索引顺序文件索引顺序文件): ordered sequential file with a primary index. 即某个搜索码上有主索引的记录文件问题1答案数据统系统2022-6-316/131索引索引有序有序，可用二分法，可用二分法(O(log(n) 比线性搜索比线性搜索O(n/2)快快Primary index: (Key, RecPos) , 有序文件，较小有序文件，较小Secondary index: (Key, RecPos . 类似一般书类似一般书书籍最后的索引书籍最后的索引non-clustering

14、 index. 小有序管大无序Index-sequential file: ordered sequential file with a primary index. 小有序管大有序数据统系统2022-6-317/131Dense index Index record appears for every search-key value in the file. 每个搜索码值都有一个索引项每个搜索码值都有一个索引项索引项索引项 与与 记录记录 1-1 对应对应问题2答案数据统系统2022-6-318/131Sparse Index: contains index records for onl

15、y some search-key values. 索引码的部分值建立索引项Key Block 块中 顺序搜索，块 可全装入内存新华字典 笔画索引，1-多 眉索引 1 1页，优点，索引文件小，可全入内存比密索引慢一点 slower than dense index for locating records.Good tradeoff: Spacetime问题2答案数据统系统2022-6-319/131例 在1971年版的新华字典中查“飞”字，利用了“ 部首检字”和“检字表”两级 索引，因而能在正文中迅速查出释义，如下图 所示。 部首检字 - 检字表第15页 - 正文111页 乙 15fei飞：

16、111一划 部首检字 检字表第15页 正文111页 密索引 飞：鸟在空中的运动-稀索引（书眉）数据统系统2022-6-320/131稀索引 Block数据统系统2022-6-321/131Compared to dense indices:比较l Less space and less maintenance overhead for insertions and deletions.节省空间l Generally slower than dense index for locating records.慢一点Good tradeoff: sparse index with an index

17、entry for every block in file, corresponding to least search-key value in the block. 细节自己看书数据统系统2022-6-322/131新华字典例子，笔画索引 是 索引的索引的索引减小索引 以便全部入内存 To reduce number of disk accesses to index records, treat primary index kept on disk as a sequential file and construct a sparse index on it.l outer index

18、a sparse index of primary indexl inner index the primary index filel 任务下达，层层传递，军师团营l 索引 与时俱进，查插删改 Indices at all levels must be updated on insertion or deletion from the file.问题3答案数据统系统2022-6-323/131新华字典例子，笔画索引 是 索引的索引的索引减小索引 以便全部入内存 To reduce number of disk accesses to index records, treat primary

19、index kept on disk as a sequential file and construct a sparse index on it.l outer index a sparse index of primary indexl inner index the primary index filel 任务下达，层层传递，军任务下达，层层传递，军师师团团营营l 索引索引 与时俱进，查插删改与时俱进，查插删改 Indices at all levels must be updated on insertion or deletion from the file.数据统系统2022-6

20、-324/131军师团营数据统系统2022-6-325/131主记录和索引 ，主仆关系，索引为主文件服务。Single-level index insertion:l 密索引 Dense indices 插主插仆 if the search-key value does not appear in the index, insert it.l 稀索引 Sparse indices 加主块（分裂），加索引l if index stores an entry for each block of the file, no change needs to be made to the index un

21、less a new block is created. In this case, the first search-key value appearing in the new block is inserted into the index.数据统系统2022-6-326/131密索引 ：主删 仆删Single-level index deletion:l Dense indices deletion of search-key is similar to file record deletion.l 稀索引 Sparse indices l if an entry for the se

22、arch key exists in the index, it is deleted by replacing the entry in the index with the next search-key value in the file (in search-key order). If the next search-key value already has an index entry, the entry is deleted instead of being replaced.Multilevel insertion (as well as deletion) algorit

23、hms are simple extensions of the single-level algorithms主删主删 ，仆调整，仆调整多层，递归处理，下层的块分裂，对应上多层，递归处理，下层的块分裂，对应上层加一项层加一项问题4答案数据统系统2022-6-327/131l Dense indices deletion of search-key:similar to file record deletion. Key对应的最一个记录被删除时，删掉它对应的最一个记录被删除时，删掉它 皮之不存，毛将焉附皮之不存，毛将焉附数据统系统2022-6-328/131非关键字搜索 、记录非顺序排列 (

24、key, RecPos ） , 如书末索引 Key RecPosl Example 2: as above, but where we want to find all accounts with a specified balance or range of balancesWe can have a secondary index with an index record for each search-key value; index record points to a bucket that contains pointers to all the actual records wi

25、th that particular search-key value.问题5答案数据统系统2022-6-329/131 次索引（1 ：多）稠密， 主稠密索引 1：1査余额700的账户 账号 支行 余额数据统系统2022-6-330/131次索引 必 密 Secondary indices have to be dense.Indices offer substantial benefits when searching for records.When a file is modified, every index on the file must be updated, Updating

26、indices imposes overhead on database modification.索引 与 主文件 同 与时俱进主索引顺序扫描 快 （因 按关键字 排序）Sequential scan using primary index is efficient, but a 次索引顺序查找 慢 sequential scan using a secondary index is expensive l each record access may fetch a new block from disk数据统系统2022-6-331/131Basic Concepts 基本概念Order

27、ed Indices 顺序索引B+-Tree Index Files B-树索引B-Tree Index Files B-树文件Static Hashing 静态散列Dynamic Hashing 动态散列Comparison of Ordered Indexing and Hashing 比较Index Definition in SQL SQL 中的索引Multiple-Key Access 多关键字存取数据统系统2022-6-332/131indexed-sequential files: 小有序 管 大有序顺序索引的缺点 ：索引变大 效率降低，溢出块太多， 需要定期re-index B

28、+-tree 优点 ，平、 半、 序 在生长中保持 平衡，装载因子 过半 ，有序 自动重组，局部更新 与时俱进B+-tree的小缺点 结点分裂合并时的开销大l 插入删除时可能递归作几次，装载因子5075%l 利大于弊， 广泛采用是多级索引的特例数据统系统2022-6-333/131indexed-sequential files: 小有序 管 大有序顺序索引的缺点 ：索引变大 效率降低，溢出快太多， 需要定期re-index B+-tree 优点优点 ，平、 半、 序 在生长中保持 平衡，装载因子 过半 ，有序 自动重组，局部更新 与时俱进B+-tree的小缺点的小缺点 结点分裂合并时的开销大

29、l 插入删除时可能递归作几次，装载因子5075%l 利大于弊， 广泛采用问题6答案数据统系统2022-6-334/131叶根距 一致 ，平衡性， All paths from root to leaf are of the same length装载因子过半 Each node that is not a root or a leaf has between n/2 and n children.A leaf node has between (n1)/2 and n1 valuesSpecial cases: 特例l 根非叶，有2 子节点。简单l 只有一个节点时，根即叶，含 0 (n1) 个

30、值.l 注意Hbase中是B-树， 不是B+树，实现上容易一些B+-tree 是满足下列条件的有根树:问题7答案数据统系统2022-6-335/131Typical nodel Ki are the search-key values l Pi are pointers to children (for non-leaf nodes) or pointers to records or buckets of records (for leaf nodes).The search-keys in a node are ordered K1 K2 K3 . . . Kn1 关键字排序关键字排序n

31、个指针个指针关键字 n-1 个数据统系统2022-6-336/131For i = 1, 2, . . ., n1, pointer Pi either points to a file record with search-key value Ki, or to a bucket of pointers to file records, each record having search-key value Ki. Only need bucket structure if search-key does not form a primary key.If Li, Lj are leaf n

32、odes and i k.If such a value exists, assume it is Ki. Then set N = PiOtherwise k Kn1. Set N = Pn Until N is a leaf nodel If for some i, key Ki = k follow pointer Pi to the desired record or bucket. l Else no record with search-key value k exists.数据统系统2022-6-344/131关于部队编制的常识 来说明 B+-树在插入或删除时，节点的分裂与合并

33、以及B+树高度的增减和根节点浮动等递归过程。 部队的编制。 叶节点为连队。 三三制一 个团至多三个营，至少二个营，一个营应至多三个连，至少二个连， 表示缺编的空白位置。 在 (a)中，根节点为团级，叶节点为连级。以部队番号（即层次序列码）为关键字， 例如， 1团2营4连 （理解为字符串） 数据统系统2022-6-345/131 连 ( a ) (b). 增加第9 、10连后 图5.3 一个编制树, 后面解释1 2 3 4 5 6 7 8 .1 2 34 5 6 7 89 101 团1 师1 团2 团4营3营2营1 营3营2营1营数据统系统2022-6-346/131易知，上述的编制树摹拟了B+

34、-树三大特点（平衡性，过半性，顺序性）。 1.搜索 查找关键字 k=1团 2 营 4 连的项。按字典序比较关键字，利用顺序性， (1) 按字典序， 2团 K 1 团，搜索以1 团为根的子树 ； (2) 因 1团2营 K 1团3营，问题递归地化为搜索以 1团2营为根的子树； (3) 该子树为叶节点，通过二分法（二次）查得第一索引项为所求。 1 2 34 5 67 8 .1 团3营2营1营数据统系统2022-6-347/131易知，上述的编制树摹拟了B-树三大特点（平衡性，过半性，顺序性）。 1.搜索 查找关键字 k=1团 2 营 4 连的项。按字典序比较关键字，利用顺序性， (1) 按字典序，

35、2团 K 1 团，搜索以1 团为根的子树 ； (2) 因 1团2营 K 1团3营，问题递归地化为搜索以 1团2营为根的子树； (3) 该子树为叶节点，通过二分法（二次）查得第一索引项为所求。 1 2 34 5 67 8 .1 团3营2营1营数据统系统2022-6-348/131给定关键字 search-key，求记录号（或记录指针）.l 从根起, l 如果 search-key 结点中最大Key,沿最右子树搜索l 否则 搜索 Kj=Min( k | K search-key)，必存在l 则 以Pi为子树根，递归 查找l 最后到叶结点 l 如存在 i, Ki = k ，沿指针 Pi 到主文件中目

36、标桶l 否则 搜索目标不存在数据统系统2022-6-349/1312.不发生节点分裂的插入不发生节点分裂的插入 插入 关键字 K= 1团3营9连 的索引项。先搜索K 所在项，得到其位置在 处,现为空白，填入 K=9即可。3. 发生节点分裂的插入 再插入 K= 1团3营10连 的索引项。按关键字搜索，似应插入到 1团3营9连 右方。但如此 则 3营有 4个连，超编 1 2 34 5 67 8 .1 团3营2营1营问题9答案数据统系统2022-6-350/1312.不发生节点分裂的插入不发生节点分裂的插入 插入 关键字 K= 1团3营9连 的索引项。先搜索K 所在项，得到其位置在 处,现为空白，填

37、入 K=9即可。3. 发生节点分裂的插入 再插入 K= 1团3营10连 的索引项。按关键字搜索，似应插入到 1团3营9连 右方。但如此 则 3营有 4个连，1 2 34 5 67 8 .1 团3营2营1营超编数据统系统2022-6-351/131分裂节点如下： 从3 营中分出 9、10连作为第4 营。问题递归到上一层次，即增加第4 营，于是1 团中有4 个营，超编。分为1 团、2 团新设一个师作为根节点。结果如 图 ,1 2 34 5 67 89 101 师1 团2 团4营3营2营1 营此师战斗实力甚 虚 数据统系统2022-6-352/131分裂节点如下： 从3 营中分出 9、10连作为第4

38、 营。问题递归到上一层次，即增加第4 营，于是1 团中有4 个营，超编。分为1 团、2 团新设一个师作为根节点。结果如 图 ,1 2 34 5 67 89 101 师1 团2 团4营3营2营1 营数据统系统2022-6-353/131当从(b) 中删除10连后，4 营缺编，4营与3营合并，从而造2团缺编，2团与1团合并， 于是1 师缺编，从而取1师编制。结果相当于在图5.3 (a)中增加了第9连。 1 2 34 5 67 8 91 团3营2营1营数据统系统2022-6-354/131在上面结果中再删除1团3营9连，搜索到位后，改9 连为空白。结果如图5 3(a)所示 以上 递归过程的 思路和大

39、方向。下面讲 合并与合并与 分裂时分裂时 索引项升索引项升降，重新安排降，重新安排 等技术细节。 1 2 34 5 67 8 1 团3营2营1营数据统系统2022-6-355/131在上面的部队编制例子中，为了借助于常识，采用了三三制。一个节点的最大子节点数为奇数。 但是实用中，如在HBASE中（及其它 一些 实际DBMS ）规定一个节点上允许的最多索引项数为偶数偶数偶数 好计算好计算 半节点（移位）半节点（移位）数据统系统2022-6-356/131为了使例子简单、原理清楚，下面假定：B+-树的一个节点上最多四项，最少两项。相当于一个非根节点的团最多5个营（节点上四个，节点再带一个左边儿子）

40、，最少2个营。 数据统系统2022-6-357/1316. 节点分裂时中项晋级，节点数增加，根节点可能浮动 k1 n1.k2 n2.k3 n3.k4 n4 k3 n3k1 n1.k2 n2.K4 n4.k5 n5插入(k5,n5) 后, 节点分裂, 中项 (k3, n3) 升为父项 （保持顺序性）数据统系统2022-6-358/131上页，上一层次为空， (k3,n3)成为新的根节点，且其中只有一个索引项，这就是为什么 根点装载率可以不过半的原因。 由此可见，在插入索引项时，节点数可能增加，根节点可能浮动。节点数可能增加，根节点可能浮动。 数据统系统2022-6-359/131从图 中删去(k

41、5,n5)，其所在的结点非根节点且项数不过半，因而缺编。问题“反映”到上一级,（在程序中为递归和回溯）需在以(k3, n3)为根的子树中来处 理缺编问题，向左第或右兄借,(要维持过半性和顺序性)。 但此例中借不出，上级节点中的(k3,n3)项“因损失部属因损失部属而引咎辞职，下放以充实基层而引咎辞职，下放以充实基层”。 k3 n3k1 n1.k2 n2.K4 n4.k5 n5数据统系统2022-6-360/131“删除操作后，删除操作后，B+树中内节点的树中内节点的Key值，值， 可能在叶节点上不可能在叶节点上不存在存在”。 这是实现时，厂商的策略这是实现时，厂商的策略。 内节点上Key作分水

42、岭值， 目的是 能分出左右边 如果加一道函数： check ( ) if (内节点的内节点的Key1值，不出现在叶节点上）值，不出现在叶节点上） 把把Key1 换成有子树中换成有子树中 叶上最小叶上最小Key 有些开发商认为，这道程序不调用也不会出错， 还可以省时间。所以出现了这种情况。 B+树强调树强调 节省空间，中间节点节省空间，中间节点 完全不出现在叶节点上完全不出现在叶节点上。数据统系统2022-6-361/131一般，一个大数据库（100G) 的索引 (2-10G) 不能全部进入内存，驻留磁盘。 因此检索瓶颈是 读写盘块数（大约是B+-树的高度，大约为关键字总数的对数， 下面分析数据

43、统系统2022-6-362/131给定一个查询 ，产生 一条从根到某个叶的路径如果总的关键字为 K 个，每个结点上至少（n/2)项，则路径长度则路径长度 或树高或树高 HT= logn/2(K). （下页证明）一般结点大小512b 4 kb , n =128 ( 半个结点装的项数）当 100 万 记录 n = 100, 最多log50(1,000,000) = 4 个结点从磁盘读到内存 用二分法搜索，可能读20个结点（220=10242 100万每读一个磁盘块大约 20 毫秒数据统系统2022-6-363/131 设m= n/22层 m2 项3层 m3 项p层 mp项如果总的关键字为如果总的关

44、键字为 K 个个,部分小于全量部分小于全量叶节点数量 mpK , 路径长度(树高 Hight)，即读块数 HT = plogm(K) . . .数据统系统2022-6-364/131前面已经讲过，1 . 先搜索 待插入项应该 出现 的叶结点2 如果找到了，则不重复，不再插入，否则插入，3 如果超编。分裂结点，递归我们已经通过补充的例子解释了思想，后面几个页面留作自学数据统系统2022-6-365/131Splitting a node:分裂结点， 一分为二，中项晋升Result of splitting node containing Brighton and Downtown on inse

45、rting Clearview数据统系统2022-6-366/131B+-Tree before and after insertion of “Clearview”新插入项目数据统系统2022-6-367/131Before and after deleting “Downtown” cp253数据统系统2022-6-368/131Deletion of “Perryridge” from result of previous example 导致根结点 ，缺编， 被取消数据统系统2022-6-369/131underfull,缺编 向左兄借，其孙子跟着转户口Before and after

46、 deletion of “Perryridge” from earlier example数据统系统2022-6-370/131传统索引文件用 一段时间，性能退化（ degradation）.但B+-树在生长中保持 “平、 半、 序”把主记录存在B+-树叶结点中，主索合一 数据统系统2022-6-371/131叶节点中存主记录 优点 节省一些空间缺点 当叶节点分类合并时，代价大 （辅助索引解决 参见 CP334）Example of B+-tree File Organization3/2n数据统系统2022-6-372/131Variable length strings as keys

47、实践中， 关键字是变长串l Variable fanoutl Use space utilization as criterion for splitting, not number of pointersPrefix compression 可压缩可压缩 节省存储空间节省存储空间l Key values at internal nodes can be prefixes of full keyKeep enough characters to distinguish entries in the subtrees separated by the key valueE.g. “Silas”

48、and “Silberschatz” can be separated by “Silb”l Keys in leaf node can be compressed by sharing common prefixes数据统系统2022-6-373/131类似B+.但项目在树中出现一次，节约空间非页结点中，头尾都是指针，指针比项目多一个关键字通常预留56字节，多的一个指针 节省一个关键字空间Nonleaf node pointers Bi are the bucket or file record pointers.数据统系统2022-6-374/131B树 算法复杂一些， 为了节约空间， 随

49、机访问 速度并不慢 顺序访问 比B+树慢 （B+树 可以简单顺序搜索叶节点） 如移动设备上， 用B树 节约空间 是可行的 数据统系统2022-6-375/131B-tree (above) and B+-tree (below) on same dataB+，3层B树 2层数据统系统2022-6-376/131Advantages of B-Tree indices:l 比 B+-Tree 结点少，不到叶 ，也可以找到一些指针.Disadvantages of B-Tree indices:l 提前找到的只是一小部分（非叶结点只有 1/(2*n) )l 非叶结点占内存多，项目数少一些，层数多一

50、些插入删除复杂一点l 实现难一点l Typically, advantages of B-Trees do not out weigh disadvantages. 与B+相比，弊大于利数据统系统2022-6-377/131用合成关键字 快用两个单个的关键字. 较快效率 与次序有关，如where branch-name = “Perryridge” and balance 1000较快where branch-name “Perryridge” and balance = 1000慢， 这里的结果是较大集合数据统系统2022-6-378/131 多个单码索引： 如 “姓名” 建一个缩影， “年龄” 建一个索引多码缩影 如 KeyStr= “姓名”+ “年龄” , 建一个索引数据统系统2022-6-379/131 With the where clause where branch_name = “Perryridge” and balance = 1000the index on (branch_name, balance) can be used to fetch only records that satisfy both conditions.Using separate indices in less efficient we may fetch many reco