数据库之索引篇.ppt

能使用B-Tree索引的查询 ● 匹配全名 ● 匹配最左前缀 ● 匹配范围值 ● 精确匹配一部分并且匹配某个范围中的另一部分 ● 只访问索引的查询 局限性 ● 如果查找没有从索引列的最左边开始，它就没什么用处 ● 不能跳过索引中的列。 ● 存储引擎不能优化访问任何在第一个范围条件右边的列. 更多使用优化： /2011/06/mysql索引浅析 /?p=460 ? (二) HASH 系列 ● 基本 hash ● 可扩展 hash ● 线性 hash HASH 索引 基本hash:(静态) insert ? delete ? space utilization ? Improve ? 可扩展hash ● Hash function computes sequence of b bits for each key. Generally b =32 . ● At any time, use only the first i bits . ● Introduce indirection by a pointer array Pointer array grows and shrinks (size 2^i ) ● Pointers may share data blocks (store number of bits used for block in j ) ● Use pointer directory . 需要?位才能确定记录在该桶？局部深度 可扩展hash的结构 可扩展hash 的插入 ●直接插入 ●页(桶)分裂 – 局部深度( ? )加1 ●目录分裂(?+1i) – 放大目录，深度( i )加1 性能分析 优点： 当查找记录时，只需查找一个存储块。 缺点： 1当散列值分布不均匀或偏斜很大时，会导致目录项数特别大和数据桶的空间利用率很低。 2 每次目录调整都是翻倍调整，目录大小扩展过快，调整不平滑。 线性 hash ● Linear Hashing is a dynamically updateable disk- based index structure which implements a hashing scheme and which grows or shrinks one bucket at a time. ●The index is used to support exact match queries , i.e. nd the record with a given key. Compared with the B+-tree index which also supports exact match queries (in logarithmic number of I/Os), Linear Hashing has better expected query cost O(1) I/O. 与可扩展散列相比，线性散列不需要存放数据桶指针的专门目录项且能更自然处理数据桶已满的情况. 但如果数据项键值散列后分布不均匀的偏斜度大，导致的问题可能会比扩展散列还严重。 h(k)仍是二进制位序列，但使用右边(低)i位区分桶 。 1) 桶数＝n，h(k)的右i位＝m 2) 若mn，则记录位于第m个桶 3) 若n ? m 2i,则记录位于第 m-2i-1 个桶 4) n的选择：总是使n与当前记录总数r保持某个固定比 意味着只有当桶的填充度达到某个比例后桶数才开始增长 。 线性 hash 线性 hash i：当前被使用的散列函数值的位数，从低位开始 n：当前的桶数 r：当前散列表中的记录总数 r/n 1.7 插入过程 ●直接插入 ●增加溢出块 ●增加新桶，分裂旧桶（提升m值） ●提升当前被使用的散列函数的位数 i 参考文献 /?post=74 /v_JULY_v/article/details/6530142 /hguisu/article/details/7786014 /sql/learn-sql-server/understanding-full-text-indexing-in-sql-server/ :8080/home/donghui/publications/books/e_ds_lin