开发者学堂课程【高校精品课-西安交通大学-数据库理论与技术：第八课】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/12/detail/15864
第八课（三）
内容介绍：
一、B+树插入数值过程
二、B+数之键值删除与结点合并过程
三、散列索引
三、散列索引
假定有 M 个桶，每个桶有相同容量的存储（可以是内存页，也可以是磁盘块），现有一个散列函数H，可以将关键字值映射到0-m-1的值，存的时候告诉地方，当你查找的时候，用散列函数一算，就可以知道具体位置。以上是原理。
告诉你常量在哪，然后到对应地方去找，这就是散列函数最简单的函数，永远是随机的，但其实并不随机，因为只要关键字值不变，那么算出的值一定是这个值。将散列值为k的记录存放到k的桶当中，这就是散列的过程和原理。
如果主桶满了的话，就会溢出，会增加桶，成为溢出桶。所以散列函数不均衡的话，就会出现问题，尽可能让数据均匀放置。目标是选择一个适合的散列函数，将一个集合均匀的映射到桶内，对于任何一个关键值，映射到对应位置的概率应该几乎相等，这就是散列，散列的布置很迅速。后续还有许多别的用处，在讲区块链的时候，原理的时候还要用到散列，防串感的时候，将值散列之后，存散列值得时候，感应出来之后，算出来的值不一样，如果算出来的值一样的话，就说明没有改动。如果进行改动还能凑成一样的数值，这是一个极难的工作，如果把这个问题解决了的话，就是一个重大突破。
>内存数据可采用散列确定存储页，主文件可采用散列确定存储块，索引亦可
采用散列确定索引项的存储块
>M个桶。一个桶可以是一个存储块，亦可是若干个连续的存储块。
实例：假设 1存储块可存放2个键值及其指针
M=4;1个桶为1个存储块
h(x)满足：
✔h(e)=0； h(b)=h(f)=h(s)=1
✔h(g)=2;h(a)=h(c)=3
如何查找关键值 a 的索引项？
计算 h（a）=3
读取3号值，获得数值a的索引项
需要1个磁盘块读取
如果要进行插入，值为2的话，2号桶有空间，则直接插入2号桶。
●问：如何插入键值d的索引项？
✔计算 h(d)=2
✔如2号桶有空间，则将索引项 d 插入2号桶中●问：如何插入键值s的索引项？
V计算 h(s)=1
√1号桶无空间，则申请一溢出桶，插入s
●问：如何删除键值f.
v计算 h(f)=1
v删除1号桶中的键值f
将溢出桶中的s合并到主桶中，删除溢出桶
A
那么接下来散列索引的目标，最好是没有溢出，如果溢出的话，影响效率。怎么样才能均匀一点呢，那么就涉及到一系列算法，多次进行散列。通的数目如何确定，第一是跟地址空间大小有关系，比如说键值和桶的数目的比值，假如说有10000个数目，就10000个桶，随着改变。
散列索引的目标：最好是没有溢出桶，每一个散列值仅有一个桶。读写每一个键值都只读写一个存储块。
>均匀分布如何做到？ 期望将所有数据分布均匀地存储于M个桶中，使每一个桶的数据成为具有某种特征值h(k)的数据集合。---散列函数的选择。
√桶的数目 M 如何确定？在键值几倍于桶的数目时，每个散列值都可能多于一个桶，形成一个主桶和多个溢出桶的列表，此时需要二次检索：先散列找到主桶号，再依据链表逐一找到每个溢出桶。---桶的数目的确定。
下面是一个数目的问题，桶的数目怎么确定，如果m值不变，叫静态散列，容易实现，缺点明显，如果 m 不变，m过大则浪费，m 过小，则产生更多溢出桶，影响效率。弄一个动态，可以进行动态变化，根据具体情况进行变化，跟上面的 B+树一样。有一个问题是桶的数目和函数值相关的，如果 m 变化，那么原来的位置就不应该变化。就相当于将房子增加到20座，那么原来空的房子就有其他人来住，这是存储内容要变化。那么存储内容是否改变呢？是否需要将已经存储的数据再放到新的桶在进行存储呢？
桶的数目M是固定值…静态散列索引
·如果桶的数目M不变：M 过大，则浪费；M 过小，则将产生更多的溢出桶，增加散列索引检索的时间。
桶的数目随键值增多，动态增加…动态散列索引
·h(k)是和桶的数目M相关的。M的变化会否影响原来存储的内容呢？·是否需要将原来已经散列-存储的数据按新的桶数重新进行散列-存储呢？
上述问题如何进行处理呢，就是接下来的可扩展散列索引，如果 m 不可变，过大浪费过小影响效率。那么就需要m变化，这个可扩展散列分为可扩展散列索引和线性散列索引。先看可扩展索引，这个基本思想是在桶中引入一个间接层，主要是通过二进制的方法，进行散列控件，i只有一个桶，满了之后就进行分裂，即 i+1。最低的一位和最高的一位，当又满了之后，再分裂，i 变2，即4位，都是保留2的i次方。i 就是当前有效对数，初始值为1，满了之后就增加对数。这是基本思想，细节就涉及到分裂的时候，不是全部都分裂，有一些细节。以上是一个主要过程。
为桶引入一间接层，即用一个指向块的指针数组来表示桶，而不是用数据块本身组成的数组来表示桶。
•指针数组能增长，其长度总是2的幂。因而数组每增长一次，桶的数目就翻倍不过，并非每个桶都有一个数据块；如果某些桶中的所有记录可以放在一个块中，则这些桶可能共享一个块。
•散列函数 h 为每个键计算出一个 K 位二进制序列，该 K 足够大，比如32。但是桶的数目总是使用从序列第一位或最后一位算起的若干位，此位数小于 K，比如说i位。也就是说，当i是使用的位数时，桶数组将有2的i次方个项。
上面涉及到2的次方，是因为主要运用到了二进制，更便于处理，那么桶的数目，就是翻倍，并不是每一个桶都有一个数据块，可以共享。意思是有的指针有多个，但是都指向同一个桶，不需要分的就不分。散列函数 h 为每个键计算出一个 K 位二进制序列，就可以算一个32位的，那么桶的数目就是从序列第一位或最后一位算起的若干位，此位数小于 K，比如说i位。这是基本的思想。
例子如下：
俩个参数 k 和 i。最高位为 k，现在的参数是i，那么当前桶数就是2的 i 次方，初始值可以假定 i 为1，也可以是0。因为0和1有俩个桶，只要最高位为0，就往0放，最高位为1就往1放。0对应0（010）,1对应1（011），标注的1表示最高的只用了1位，索引号和地址空间。这个是虚拟的，那么这个索引号取前i位，根据i的位次去选择，当i等于2的时候，就有四位，四个的时候就要进行分转。
具体代入数据之后，假设 k=4，i=1，则 n=2的 i 次方=2，现在插入1110，最高位是1，i的最高位1，定位之后，插入好。插入1010,的话，会发现桶满了，进行分裂，就跟前面的B树一样，就要i+1，就变成2,4个桶。
编的时候，最高位的0001、1011这样编码，原来1号值进行拆分了，原来俩个关键字值放不下，拆分成俩个桶。11、10分别放，用的是俩位。原来俩个桶的没有加东西，所以不变，仍然最高只用一位。
上述是他的拆分过程。
