数据库系统概念之索引与散列

数据库系统概念之索引与散列

文章目录

• 基本概念
• • 索引类型
  • 索引好坏衡量标准
• 顺序索引
• • 索引种类
  • 索引的更新
  • • 插入
    • 删除
    • 多级索引的插入和删除
  • 多码上的索引
• B+树索引
• • B+树的结构
  • • 叶结点
    • 非叶结点
  • B+树的查询
  • B+树的更新
  • 不唯一的搜索码
• B+树扩展
• • B+树文件组织
  • 辅助索引和记录重定位
  • B+树索引的批量加载
  • B树索引文件
• 散列索引
• • 静态散列
  • • 散列函数
    • 桶溢出
  • 动态散列
  • • 可扩充散列
    • 可扩充散列查询和更新
  • 静态散列和动态散列比较
  • 顺序索引和散列的比较
  • 位图索引
• 参考

基本概念

索引是由于需要快速访问文件中的记录(行)这种需求而产生的，通过索引可以快速定位到文件中的某条记录在哪个块中

索引类型

有两种基本的索引类型：

1. 顺序索引：根据值的顺序对记录进行顺序排序，然后建立的索引，也可以是值不排序，但是对值的索引进行顺序排序，索引存储者记录中的某个值，和该记录所在的地址
2. 散列索引：根据记录中的某些值，将其通过hash函数计算后得到存储的位置

索引好坏衡量标准

1. 访问类型(access type)：能够有效支持的访问类型，包括值范围和范围访问，如顺序索引可以值访问，也就是值访问一个值，也可以范围访问，但是散列索引如果想范围访问只能一个一个找，查找速度绝对没有顺序索引快
2. 访问时间(access time)：在查询时使用索引找到值或一个范围的值所用的时间
3. 插入时间(insertion time)：插入一个新的数据项并建立其索引(或者修改索引结构)所需的时间
4. 删除时间(deletion time)：删除一个新数据项所需的时间，并删除其索引(或修改索引结构)所需的时间
5. 空间开销(space overhead)：索引结构所占用的额外存储空间

顺序索引

在这里要知道搜索码(search key)的概念，搜索码就是用于搜索记录的属性(字段或列名)，也就是被建立索引的一张表的列，一张表可能有多张搜索码

索引种类

1. 聚集索引(clustering index)：也被称为主索引(primary index)，也就是常听到的聚簇索引，指的是记录的物理存储顺序和索引排列索引一样，这种索引不管是值查询还是范围查询都很快，因为物理上有序，一般我们主键索引就是聚集索引，一般建立一张表时，mysql会根据主键顺序，将记录在物理顺序上排序，也就是建立聚集索引，建立聚集索引的文件也叫索引顺序文件，即文件上的记录顺序和索引一模一样
2. 非聚集索引(nonclustering index)：也被称为辅助索引(secondary index)，也就是常听到的二级索引，虽然建立的索引是根据搜索码来排序的，但是其实物理存储上，不是根据该搜索码排序的，一个表可以有多个非聚集索引，但是只能有一个聚集索引，因为物理顺序只能有一种
3. 稠密索引(dense index)：每个搜索码都对应一个索引项，下面两个索引和上面两个分类方式完全不同要注意区分。在稠密索引由于每个搜索码都对应一个索引项，但是如果搜索码相同呢，在稠密聚集索引中，如果搜索码相同，那么我们只需要在搜索码相同的第一个记录上有一个索引就行，因为记录物理上是按该搜索码排序的，所以可以指向第一个后，可以慢慢往后找。但如果在稠密非聚集索引中，由于在物理上不按该搜索码排序，所以搜索码相同时，该搜索码需要指向一个具有所有相同搜索码的记录的指针列表。所以每个搜索码对应一个索引项，索引项里面可能包含一条记录，也可能包含一个指针列表，注意是一个搜索码对应一个索引项，而不是一条记录(行)对应一个索引项
4. 稀疏索引(sparse index)：稀疏索引只有在聚集索引是才能使用，因为稀疏索引只为其中一些搜索码建立索引项，除非记录本来在物理上就有序，否则无法使用稀疏索引，如果记录在物理上有序，通过稀疏索引定位到大概位置后，可以使用物理顺序往后找，直到找到自己要找的记录。建立稀疏索引，有利于减少索引占有空间
5. 多级索引(multilevel index)：当索引非常多的时候，索引会非常大，我们无法把索引全部放入内存，所以可以在索引上面重新建立稀疏索引，因为索引绝对是有序的，但是索引所对应的记录不一定有序，即上面的聚集和非聚集索引的区别，这样我们可以把索引的索引放入内存，然后查找时找到对应索引，再把要的索引放入内存，再通过这个索引去找物理上的记录。要知道查询的快慢基本上是由访问的磁盘的次数决定的，因为内存随机访问速度是磁盘随机访问速度的10万倍，内存顺序访问速度是磁盘顺序访问的6-7倍，所以我们可以把多级索引的一些根索引先放入内存，这样可以减少磁盘范围次数

索引的更新

索引的更新的同时,也包括数据的更新

插入

为了插入一条记录，系统先用待插入记录中的搜索码值进行查找，并根据索引是稠密索引还是稀疏索引而进行下一个 *** 作

1. 稠密索引：如果该搜索码值不在索引中，系统就在索引中合适位置加入具有该搜索码值的索引项，如果该搜索码在索引中，则分为两种情况是聚集索引还是非聚集索引，聚集索引的索引项值存储一个指向具有相同搜索码值的第一条记录的指针，则无须更新索引，只需把插入的记录放到具有相同搜索码的其他记录之后，如果是非聚集索引，非聚集索引的索引项是存储着具有相同搜索码的记录的指针集合，此时需要更新索引和数据，需要将新插入的记录的指针添加进该索引项的集合，并且将记录按照聚集索引(主键索引)的顺序插入表中
2. 稀疏索引：稀疏索引的插入一定要是聚集索引才可能发生的，一般是为每个块保存一个稀疏索引，块的大小一般是(4KB-8KB)里面可以存放很多个记录，并且是数据库读取的最小单位。所以稀疏索引只有在创建一个新的块的时候才会创建一个稀疏索引，更新稀疏索引发生在，插入了一条记录，该记录的搜索码是在该块中最小的，此时会更新该块的稀疏索引指向该记录

删除

为了删除一条记录，系统首先查找要删除的记录，然后下一步的 *** 作取决于索引是稠密索引还是稀疏索引

1. 稠密索引：如果被删除的记录是具有这个特定搜索码值的唯一的一条记录，系统就从索引中删除该索引项，此时就无须分聚集索引还是非聚集索引了，如果被删除的记录的搜索码值还有其他记录也具有，则需要考虑聚集索引和非聚集索引，聚集索引项的指针指向具有该搜索码的第一条记录，如果刚好要删除的就是该记录，则需要移动聚集索引项的指针指向该搜索码的第二条记录，如果不是要删除具有该搜索码的第一条记录，则无须更新索引，非聚集索引项中含有指针列表，所以一定要更新索引，从指针列表中删除该指针
2. 稀疏索引：由于一般一个块对应一个稀疏索引，则会有四种情况，一种是要删除的记录上根本就没有稀疏索引即该记录不是该块中第一个记录，则无须修改索引只需要删除记录即可，第二种是要删除的记录是块中第一个记录而且后面的一个记录的搜索码和该记录搜索码相同，则稀疏索引项里的指针指向后一个记录再删除原先要删除的记录，第三种是要删除的记录是块中第一个记录而且后面一个记录的搜索码和要删除的记录搜索码不同，则稀疏索引项里的指针指向后一个记录并且稀疏索引项里面的搜索码也要改变，然后删除记录即可，第四种是该块里面只有一个记录，则删除该记录必须删除该块，也必须删除稀疏索引

多级索引的插入和删除

1. 上述算法其重点是要分清是稠密索引还是稀疏索引，如果是稠密索引要分清楚是聚集索引还是非聚集索引，如果是稠密聚集索引则索引项最多包含一个指针，如果是稠密非聚集索引，则索引项包含一个指针集合，如果是稀疏索引则重点是要知道只有稀疏聚集索引，没有稀疏非聚集索引，并且一个稀疏索引对应一个块，稀疏索引的创建对应一个块的创建，稀疏索引的删除对应一个块的删除
2. 多级索引的插入和删除是对上述算法的简单扩充，对多层索引来说，底层索引可以当作上层索引的文件，上层索引可以当作底层索引的索引，所以就可以使用上面的算法进行处理了

多码上的索引

1. 多码上的索引就是我们平常说的联合索引，也就是复合索引(包括复合主键和复合二级索引)，一个搜索码可以有多个属性(多列)，一个包含多个属性的搜索码被称为复合搜索码(composite search key)
2. 复合搜索码(列1，列2），当列1不同时不比较列2，当列1相同时，才按照列2进行排序
3. 多码上的索引自然也分聚集索引和非聚集索引

B+树索引

1. 索引顺序文件组织最大的缺点在于，随着文件的增大，索引查找性能和数据顺序扫描性能都会下降
2. 因为索引顺序文件组织，可能使用链表组织，因为链表在更新的时候很方便，只需要把记录放在一个位置，该位置不是物理相邻的，然后把指针指向该位置就行，但是随着更新次数增加，虽然指针指向有序，但其实各个记录的散落在不同的地方，所以顺序扫描查找性能会下降，此时就需要将记录按照主键顺序在物理上重新排序，才能提高索引查找性能和数据顺序扫描性能
3. 但是B+树索引，虽然增加了平时的数据插入的和删除的开销，但是在文件比较大的时候仍然能保证比较好的执行效率(包括插入、删除、查询)，因为B+树索引在插入和删除的同时，会调整B+树的结构，不必像索引顺序文件组织一样，在一定更新次数后必须重组文件
4. B+树结构会增加插入和删除处理的性能开销，同时会增加空间开销，但是可以保证在更新频率较高的文件下，仍然保持查询性能
5. 此外B+树的有些结点是半空的，因为B+树的一个结点一般是一个块，因为数据库每次读取最小的单位是块，当一个结点中的数据小于半满的的状态，会找其兄弟结点进行合并，当一个结点的数据接近满的状态时，会分裂成两个结点
6. B+树的结点即可能只储存指向物理数据块的指针，也可能直接把物理数据块存放在B+树的结点中，这取决于B+树算法的具体实现，一般是后者(直接使用B+树来组织文件)，因为可以减少一次磁盘读取
7. B+树的非叶子节点，全部都是索引，叶子结点全是记录，各个叶子结点之间使用链表相连
8. B树是为了去除B+树在非叶子结点的冗余，直接将记录存在非叶子结点，但是这样减少了非叶子结点的索引数量，不太利于整体的查询，虽然对某些记录来说，查询需要遍历的高度较少，但是对整体来说变多了
9. 在数据库查询时，查询的主要时间花费在内存，所以一层B+树对应一次磁盘访问，所以一般数据库系统会提前缓存根结点，以及下面一两层索引结点，这样便可以减少磁盘访问次数了，B树会让整体树的高度变高，所以虽然省了一些空间，但是对性能来说得不偿失
10. B+ 树的B是balance平衡的意思，B+是二叉搜索树的改进版，将二叉搜索树的的高度压缩到极致，同时具有自动调整结构保持平衡的能力

B+树的结构 叶结点

1. B+树一个节点对应一个物理上的块，而它的叶节点则是按照主键的顺序排列的
2. 考虑第一种B+树版本，即B+树叶子结点存储着搜索码的值和用于按照搜索码顺序连接连接叶子结点的指针，还有许多指向记录所在位置的指针，第二种版本直接存储记录在叶子结点中
3. 第一种版本，B+树上面每个结点上的元素(搜索码的值和指针)是有数量限制的，即太少会和兄弟结点融合，太多会分裂成两个结点，第二种版本使用B+树来组织记录，则此时不是根据记录个数来决定是否分裂了，而是根据记录的长度，当一个物理块里面的空间小于半满则合并，接近满则分裂

非叶结点

1. B+树的非叶子结点(nonleaf node)形成了叶子结点上的一个多级(稀疏)索引，因为叶子结点有序，第一种版本是搜索码的值有序，并且有指向物理记录的指针，这种多用于二级索引，也就是辅助索引，第二种版本是整个记录按照主键排序，这种多用于聚集索引，也就是聚簇索引
2. 非叶子结点容纳指针的数量也是最少半满，最多接近满，太少则合并，太多则分裂
3. 但是根结点是特例，根节点包含的指针数量可以少于半满

B+树的查询

1. 从根节点出发，检查要查找的值V，和根节点上各个搜索码的大小比较，找到一个刚刚好比这个V小的搜索码，刚刚好的意思是下一个搜索码的值就大于V了，通过找到的这个搜索码里面包含的指向下一层节点的指针，再去下一层找刚刚好比这个V小的搜索码，直到找到叶子节点为止
2. 实际上只需访问几个物理块，一层B+树需要访问一次物理块，假设一个物理块能容纳100个元素，该元素包括搜索码的值和一个指向下层节点的指针，则从一百万的搜索码中找一个记录，需要访问的节点(也就是物理块为), log50(1000000)=4，50是100/2，只需访问四个块，如果把根节点和高层索引节点存入内存，则所需访问的块更少，一次磁盘寻道的块读取需要10毫秒，所以基本上只需40毫秒就可以读取到一条记录，如果缓存了根节点，则只需30毫秒
3. 第二种版本的B+树范围查询也很简单，先找到叶子结点，将整个块读取内存，因为记录有序，如果在一个块内就找到所有范围查询所需记录则完成，没有找完，则通过叶子结点的指向后一个叶子结点的指针，直接读取后一个叶子结点到内存，重复直到读取到所有所需的范围。注意这里必须是第二种版本的B+树，而且必须是通过主键来进行范围查询，因为二级索引的顺序并不对应物理存储顺序，所以二级索引上还含义主键列值，需要查找其他数据可以回表查找，回表查找就是拿着主键列的值去主键B+树索引查询
4. 但是如果select只查询建立二级索引的列，则无须回表，因为作为一种优化，B+树二级索引上直接存储着搜索码，不存储指针，这样有两个好处，一种是防止修改B+树主键索引时，结构发生变化还必须修改二级索引指针指向B+树主键索引的对应叶子节点。第二个好处就是，可以不用回表，所以我们一般会建立复合二级索引，这样改索引上就存储着我们想要select查询的多个列，这样无须回表，虽然数据冗余占了空间，但是查询效率大大提高

B+树的更新

1. B+树的更新包括B+树的插入和删除以及数据的更新，B+树的插入和删除比查找更加复杂，因为节点可能因为插入而变得过大而需要分裂(split)或因为删除而变得过小，需要合并(coalesce)
2. 在插入之前必须查找，找到插入元素需要放置的位置，然后第一种版本就在叶子节点插入搜索码值和记录指针(改进版本没有指针，只有搜索码的值，但是非叶子节点上仍然有指针，指向下一层的节点)，插入时按照搜索码顺序插入，保证有序
3. 在删除之前必须查到到要删除的元素在哪，找到搜索码值所在的叶子节点，当然不是删除整个叶子节点，因为叶子节点包含了很多记录，一个叶子节点里面就是像数组一样，插入的时候必须把后面的记录全部往后移动一位，删除的时候必须把后面的记录全部前移一位，而B+树版本不同时只是移动的对象不同，第一种版本移动搜索码值和记录指针构成的元素，第二种版本移动整个记录，第一种版本的改进版本只移动搜索码的值，因为没有记录指针
4. 当节点可能因为插入而变得过大而需要分裂，分裂一个节点的时候，必须将新的创建的节点插入到B+树结构中，同时一个节点就对应着父节点的一个搜索码，所以新创建了一个节点用于容纳分裂后的其他记录，也就意味着也在父结点中插入了一个搜索码，如果父结点也进入满的状态，则必须分裂，像叶子节点一样，先创建一个新节点，再将新节点到B+树结构中，然后再父结点的父结点上面添加一个搜索码，该搜索码是一个节点也就是一个物理块中最小的搜索码，依次往上进行分裂，直到在根节点上再增加一个记录指针，如果根节点也分裂了，那么则需要创建一个父结点，此时B+树的高度就又高了一层了
5. 删除则相反，一个节点因为删除而变得过小，则需要合并，合并会删除一个B+树节点，同时会把父节点上面一个指针也删除了，因为一个B+树节点对应其父节点一个指针，则父节点也可能出现因过小而出现合并的情况，一直传递到根节点，如果根节点此时只有一个指针，如果第二层索引节点仍然合并，那么也会删除这唯一一个指针，也就会删除根节点，此时造成了B+树的高度减小

不唯一的搜索码

1. 上面考虑了都是搜索码唯一，但很多时候我们一列会有多个相同的值，此时搜索码不唯一
2. 当搜索码不唯一，我们首先得考虑搜索码如何存储，由于主键不可能不唯一，则无须考虑主键B+树，只需考虑二级索引B+树，二级索引B+树要分两种，第一种版本B+树，叶子节点存储搜索码和指向记录的指针，则可以有两种选择，每个相同的搜索码只存储一次，同时存储一个指针集合，该指针集合里面所有指针都是含有该相同搜索码的记录，第二种就是存储多个元素(该元素包含搜索码和指针），这多个元素它们唯一的区别就是指针指向的记录不同，但是其搜索码相同，一般选择第二种，因为第一种储存指针集合实现太复杂，需要维护一个变长的指针列表，当指针列表太长了又涉及分裂的问题，而第二种就相对于普通一样维护B+树节点就可以了。而对于第一种版本B+树的改进版本，虽然没有指向记录的指针，但是必须存储着其主键的值，因为还必须回表，存储主键的值也可以选择存储一个列表或者存储多个元素(包含相同搜索码，但是不同主键值)
3. 所以在搜索码不唯一的列建立索引，有时并不能提高效率，还会增加删除的复杂度，降低删除效率

B+树扩展 B+树文件组织

1. 上面提到的第二种版本就是用B+树来组织文件，因为索引顺序文件组织最大的缺点是随着文件增大时由于记录物理顺序会变得越来越和主键列顺序不一致，所以查询效率低下，如果使用第一种版本的B+树，由于叶子节点只存储着搜索码的值和指向记录的指针，实际上仍然没有解决顺序索引文件组织的缺点，因为指针存储着指针，实际上用于组织文件的仍然是索引文件组织方式
2. 用B+树来组织文件，很明显的变化就是记录比指针大很多，所以一个节点上存储的量会少一点，当然这只针对与叶子节点是这样的，因为叶子节点从原先的存储搜索码的值和指向记录的指针，变成直接存储记录。而对于非叶子节点，仍然没有变化，仍然是存储搜索码的值和指向记录的指针
3. 使用B+树来组织文件时，插入和删除造成的分裂和合并就是根据一个块中所占的空间来判断了，而不是根据记录的个数来判断了，因为记录可能是变长的，不同记录长度不一样，不能单纯依赖记录个数判断是否需要分裂和合并

辅助索引和记录重定位

1. B+树文件组织可能改变记录的位置，即便记录没有更新，因为在插入一条记录导致节点分裂时，节点上的其他记录可能也因此改变位置
2. 所以辅助索引B+树如果存储的是指向记录的指针，则可能插入一条记录，就可能导致需要更新很多东西，所以这里就是第一种B+树版本改版，直接在叶子节点存储着二级索引列的列值，和主键值，需要记录中其他值，拿到主键值再回表即可
3. 第一种B+树版本改版一般用于二级索引存储，第二种版本B+树用于主键索引存储，因为聚集索引也就是主键索引的定义是物理记录是按照主键索引进行排序的，而B+树的叶子节点之间就是按照搜索码排序的，如果叶子节点存储的是整个记录，则说明记录就是按照搜索码排序的，也就符合聚集索引的定义了
4. 在这里总结一下，免得混淆，第一种B+树版本就是叶子节点存储着搜索码和指向记录的指针的结构，第一种B+树版本改版就是叶子节点存储着搜索码不包括指向记录的指针，第二种B+树版本就是叶子节点直接存储着整个记录，以上三种版本的非叶子节点都是存储着搜索码和指向下一层节点的指针(不是指向记录的指针)，而B树是可以在非叶子节点直接存储记录的，B*树是B+树的基础上，在非叶子节点上增加了指向非叶子节点兄弟节点的指针，也就是链表结构，而且合并的的阈值从二分之一变成了三分之二，也就进一步提高了节点存储效率和降低了树的高度

B+树索引的批量加载

1. 在B+树中插入一条记录需要一些 *** 作，并且最坏的情况下与树的高度成正比，这通常还是比较小的（即便对于比较大的关系，一般为5次或者更少）
2. 如果随机插入记录的话，我们必须先查找该记录应该插入的块，将其读取入内存，然后再插入记录，并修改索引结构，如果要插入大量的记录的话，就会非常浪费时间
3. 将大量项一次插入到索引中称为索引的批量加载(bukl loading)，一个有效执行索引批量加载的方式如下，首先创建一个包含表索引的临时文件，然后根据构建好的索引的搜索码来排序文件，最后扫描排序好的文件并且将项插入到索引中。即先将要插入的记录排序，再一次性插入到索引中，就能比较块的插入。而排序一般使用外部排序算法，即便是对很大的文件进行排序，只要内存够大，其开销也只不过是读取几次文件相当。并且一次性插入就无须随机读取写入，可以顺序写入，随机I/O每个物理块需要10毫秒，而顺序I/O每个物理块一般只要1毫秒
4. 还有一种就是将B+树索引全部删除，然后排序记录，然后自底向上构建B+树，这比随机插入大量数据并改变索引结构要快很多

B树索引文件

1. B树索引(B-tree index)，也有误解说B树是B-树，其实并没有B-(减)树
2. B树索引和B+树索引相似，两种方法的主要区别在于B树去除了B+树搜索码值存储中的冗余，在B+树索引中每个搜索码可能既出现再在非叶子结点也出现在叶子结点，甚至可能出现在多个非叶子结点
3. 而B树为了去除这种冗余，允许搜索码值只出现一次(如果它们是唯一的)，B树允许直接将记录放在非叶子结点，这样相比B+树可以使用更少的树节点来存储所有
4. 然而由于在B树中，出现在非叶子结点中的搜索码值不会出现在其他地方，因此我们将不得不在非叶子结点增加一个指针域。附加这些指针指向文件记录或相应搜索码所对应的桶，指向文件记录很容易理解，就是存储指向记录的指针，没有使用B树来组织文件，指向相应搜索码所对应的桶，应该是指向下一层结点
5. B树的非叶子结点中存储的搜索码较少，意味着B树的深度会比B+树要大，虽然节省了空间，但是降低了效率
6. B树的删除 *** 作更加复杂，B+树中被删除的项总是出现在叶子结点，而在B树中被删除的记录可能在非叶子结点
7. B树在空间上的优势对大的索引来讲意义不大，所以许多数据库系统通常使用B+树数据结构实现索引

散列索引 静态散列

1. 顺序文件组织的一个缺点是我们必须访问索引结构来定位数据，或者必须使用二分法搜索，这将导致过多的I/O *** 作
2. 基于散列(hashing)技术的文件组织使我们能够避免访问索引结构
3. 桶(bucket)是能够存储一条或多条记录的一个存储单位，通常一个通就是磁盘块，但也可能小于或大于一个磁盘块
4. 为了插入一条搜索码为K的记录，我们可以计算h(K)，h是hash函数，计算出的结果就是存放记录的桶(块)的地址
5. 为了进行基于搜索码K的查找，我们只需计算h(K)，然后搜索具有该地址的桶
6. 删除也很简单，只需先计算h(K)找到要删除的记录的桶，读入内存删除再写回磁盘即可
7. 散列的缺点就是无法快速的进行范围访问，即使是相邻的搜索码，其通过散列函数计算出的地址可能也有很大不同。一个搜索码可以对应一个块，如果进行范围访问，可能要访问很多个块，一个优化的方式是先求出所有要找的搜索码对应的块，然后总有一些搜索码在相同的块，这样就可以一下取得多个要找的搜索码，但是相比顺序访问还是慢很多
8. 散列一般用于两个目的。第一个是在散列文件组织(hash file organization)中即用散列函数来组织文件，我们通过计算所需记录搜索码值上的一个函数直接获得包含该记录的磁盘块地址。第二个是在散列索引组织(hash index organization)中，我们把搜索码以及与它们相关联的指针组织成一个散列文件结构，即散列计算出的并不是记录的物理地址，而是记录的索引的物理地址，通过它的索引，再指向真正记录物理块地址，这个用于比较大的文件组织，因为hash函数总有hash碰撞，如果要组织很多物理块，可能会产生hash碰撞，可以把物理块里面填放的是指针，这样一个物理块就可以对应很多记录了

散列函数

由于设计时我们无法精确找到文件中讲存储哪些搜索码值，因此我们希望选择一个把搜索码分配到桶中并且具有以下两个特性的散列函数：

1. 分布是均匀的：为每个桶分配相同数量的记录
2. 分布是随机的：在一般情况下，不管搜索码值怎么分布，每个桶应该分配到的搜索码值数目几乎相同。即hash函数计算出的结果要与搜索码排序无关

桶溢出

1. 当插入一条记录到桶中时，可能如果一个桶(块)中没有足够空间，就会发生桶溢出(bucket overflow)，桶溢出有两个原因，桶不足，即每个桶都是几乎满的状态，偏斜，虽然一个桶快满了，但是还有其他的桶还剩很多空间
2. 解决桶溢出的方法可以在一个桶后面加一个桶的链表，溢出了则新增一个桶，这种解决方法被称为溢出链(overflow chaining)
3. 桶溢出这种形式的散列结构被称为闭地址(close addressing)，另一种方法称为开地址(open addressing)，即没有溢出链，当溢出时，使用下一个有空间的桶存放记录，这就类似哈希冲突的解决方案，链表法和开放寻址法，只不过Hash冲突是针对一个对象，而桶溢出针对的一个物理块，里面可以包含很多对象

动态散列

1. 前面描述的静态散列，有很大一个缺点在于我们必须在实现系统时选择确定的散列函数，此后若被索引的文件变大或变小，再想改变它就不容易了，因为散列一般都会用取余的方式，而余数一般是桶的数目在一开始必须固定，而动态散列可以动态改变桶的数目和散列函数
2. 如果我们使用对大小不断增大的数据库使用静态散列，则会有三种选择，第一种是根据当前文件大小选择散列函数，这种选择会使得性能随数据库增大而下降，因为hash冲突会越来越多。第二种是根据将来某个时刻的预计大小选择散列函数，尽管这样可以避免性能下降，但是初始时会造成相当大的空间浪费。第三种是随着文件增大，周期性地对散列结构进行重组，这些重组一般是增大余数的值即桶的数量，然后重新哈希，分配记录到新的桶
3. 动态散列(dynamic hashing)技术允许散列函数动态改变，以适应数据库增大或缩小的需要，动态散列技术其中有一种技术就是可扩充散列(extendable hashing)

可扩充散列

1. 当数据库增大或缩小时，可扩充散列通过桶的分裂和合并适应数据库大小的变化，这样可以保持空间的使用效率。此外由于重组每次仅作用于一个桶，因此所带来的性能开销较低，可以接受
2. 使用可扩充散列时，我们选择一个具有均匀性和随机性的散列函数h，但是此散列函数产生的值范围相对较大，是32位二进制整数，这就类似一致性哈希算法
3. 2的32次方超过40亿，我们不必为每一个散列值创建一个桶，而是在把记录插入文件时按需创建桶，怎么通过这个值选择桶的呢，这个一致性哈希算法有很大不同，一致性哈希算法是为机器结点计算哈希值，而请求往顺时针方向寻找对应机器结点，也就是找到一个机器结点的哈希值刚好比该请求的hash值大的结点，当然由于是个环状，也可能是大的值找小的值，因为多绕了一圈。而可扩充散列的这个32位值和这种比较大小顺时针寻找方式完全不同，32位数字，如果桶只有2个则只用最前面一位值，让后面31位无效，0表示第一个同，1表示第二个桶，如果桶扩容到4个，则使用前面两位的值，00表示第一个桶，01表示第二个桶，10表示第三个桶，11表示第四个桶，以后就依此类推

可扩充散列查询和更新

1. 为了确定含有搜索码K的桶的位置，系统取得h(K)的前i个高位，i的取值取决于前面所说的桶的数量，如果桶的数量为4，则取前面两个高位，根据高位的值去查找表，为什么不是根据高位的值直接去找桶呢，因为随着扩容缩容，一开始一个高位的值对一个一个桶，如00对应桶0，01对应桶1，当缩容时可能出现00和01都对应桶0的，所以在哈希值的高位和桶直接还存在一个映射表，当从映射表中找到对应桶(块)的地址，直接将整个桶读入内存获取其中需要的记录
2. 如果要插入一条记录，则先按上诉过程查找到存放待插入数据的桶(块)，如果该桶还有空间，则直接插入即可，如果该桶已经满了，则需要分裂，分裂的 *** 作是先多使用一位高位，如00可以分为000和001，则在表项中将00替换为000和001，然后将原来00指向的桶中的数据重新计算Hash函数放入000和001指向的两个桶，即多创建了一个桶和两个表项，这是原先表项只有00一个项会进行发分裂 *** 作，如果原先是00和01一起指向一个桶，则该桶满的时候，会将00和01分别指向两个桶，然后根据Hash函数重新计算原先里面的桶的数据，将其放入00和01指向的两个桶中，这种情况只需要多创建一个桶和改变表项中的指向的桶即可，无须创建表项
3. 如果要删除一条记录，也是先找到对应的桶，删除其中记录，如果删除该记录后桶也为空，则必须删除桶。有时桶并没有空，但是拥有记录很少，可以合并，就像000和001一样，合并的话直接将表项中的000和001替换成00，即删除000和001，添加00表项，然后把000和001指向的块中记录，复制到00指向的块，00指向的块也可以是000或001指向的块，这样可以少复制一些数据

静态散列和动态散列比较

1. 可扩充散列也就是动态散列的优点就是性能不随文件的增长而降低，此外其空间开销最小。虽然桶地址表带来了额外的开销，但该表为当前前缀长度的每个散列值存储一个指针，因此该表较小
2. 可扩充散列与其他散列形式相比，主要的空间节省是不必为将来的增长保留桶，桶的分配是动态的
3. 另一种动态散列是线性散列(linear hashing)，也就是平常用的链地址法来解决桶溢出或hash冲突，在桶空间满的时候，直接在后面链接一个新的桶

顺序索引和散列的比较

选择索引所需要考虑的点

1. 索引或散列组织的周期性重组代价是否可接受。顺序索引重组发生在随着不断更新后，物理记录实际存储顺序已经和主键索引顺序有很大不一致，实际上的顺序访问只是通过链表来维持，但只能进行逻辑的顺序访问，物理上根本不连续，此时会发生顺序索引重组，把所有记录按照主键顺序在物理上排列好(也并不是完全相邻，因为还有 *** 作系统控制，最后可能是断断续续的相邻，比散乱的读取效率还是高很多)。B+是索引重组发生在每一次对记录的更新，所以在平时多花了一点时间，不必全部攒在一起重组。散列索引的重组，静态散列几乎无法重组，因为一开始就固定了桶的数量，唯一可 *** 作的就是使用链地址和开放定址法处理溢出桶，而动态散列在静态散列的基础上，增加了一层地址表，重组 *** 作主要就是表项的增加和减少，表项的分裂和合并，以及一些桶的创建和删除
2. 插入和删除的相对效率如何，顺序索引插入可以直接在文件末尾插入，即使物理上没有按照搜索码排序，也可以通过修改指针，使其逻辑有序，删除也很简单，只需修改指针即可。B+的插入和删除和查询都是logn，需要修改索引结构。而散列索引的插入和删除 *** 作，基本上时间复杂度都是1，这里考虑全是访问磁盘的次数，而不是内存里面的时间复杂度，因为实际上读取整个块到内存，如果块中记录有序，在内存中是logM时间复杂度，如果块无序则是M时间复杂度，不过因为内存比磁盘快太多，所以不考虑内存，静态散列额外开销可能在新建桶，动态散列的额外开销包括修改地址表的开销和创建桶的开销
3. 是否愿意以增加最坏情况下的访问时间为代价优化平均访问时间。
4. 用户可能提出哪些类型的查询。这里考虑的查询有单一值的查询，多个and条件值查询和范围查询。顺序索引和B+树索引适合范围查询。而对于只需查询单个值，散列索引甚至只要1的时间复杂度。而对于多个and条件值查询，则位图索引最适合，每个位图记录一列的值情况，一般适合只有几个特定值的列，如性别列，则如果使用and条件查询多个列，则只需计算多个位图的交集，因为一个位图记录一列的信息，如果交集后仍然存在，说明该记录满足所有and条件

位图索引

1. 位图索引是一种为多列上的简单查询设计的特殊索引，为了使用位图索引，表中的记录必须按照顺序编号，如主键ID
2. 位图(bitmap)就是位的一个简单数组，第一个位的0和1表示第一条记录某列的值，如性别，可以让0表示男，1表示女，则0101，则表示了4条记录的性别列的值
3. 位图的 *** 作如果使用and连接多个条件，如果有位图0101和1011分别表示两个列的值，则如果要找 列1 = 1 and 列2 = 1 成立，则直接相交，就可以得到0001，则第四条记录满足该条件
4. 位图一般在数据库中用于表示一个行记录中的哪些属性(列)是空值，如可以0表示空值，1表示非空值

参考

《 数据库系统概念 》