查找
顺序查找
定义
- 顺序查找，又叫线性查找，常用于线性表
算法思想
- 从头到位依次往后找
实现
二分查找
定义
- 二分查找又叫折半查找
算法思想
- 对于排序后的线性表，可以找到中间数字进行比较
- 然后判断在前半段还是后半段
- 重复上述过程
实现
- 时间复杂度：O($\log_2n$)
分块查找
定义
- 分块查找，又称索引顺序查找。块内无序，块间有序
算法思想
- 在索引表中确定待查记录所属的分块
- 在块内顺序查找
B树
m叉查找树定义
- 二叉查找树的拓展，节点有多少个就有多少个分叉就是多叉查找树
- 每个节点关键字的查找可以用顺序查找也可以用折半查找
如何保证效率
- 若每个节点内关键字较少，导致树变高，要查更多层节点，效率低
- 不够平衡，树会很高，要查很多层节点
解决方案
- m叉查找树，除了根节点外，任何节点至少有[m/2]个分叉
- m叉查找树，任何一个节点，所有子树高度都要相同
B树的定义
- 每个节点至多有m棵子树，至多含有m-1个关键字
- 若根节点不是终端节点，至少有两棵子树
- 除根节点外的所有非叶节点至少有[m/2]棵子树，即至少含有[m/2] - 1个关键字
- 所有叶节点都出现在同一层次上，并且不带信息
树的高度 $h\le\log_{[m/2]}{\frac{n+1}{2} +1} $
B树的插入和删除
插入
- 新元素一定是插入到最底层的终端节点，用查找来确定插入位置
- 在插入key之后，若导致原节点关键字超过上限，则从中间位置[m/2]将其中的关键子分为两部分
- 左部分包含的关键字放在原节点中，右部分包含的关键字放到新节点中，中间位置[m/2]的节点插入原节点的父节点
- 若此时导致父节点叶超过了上限，继续分裂操作，知道根节点为止
删除
- 若被删除关键字在终端节点，则直接删除(要注意节点关键字个数是否对于下限[m/2])
- 若关键字非终端节点，则用前驱或后继来代替被删除的关键字
- 前驱：关键字左侧指针所指子树中最右下的元素
- 后继：关键字右侧指针所指子树中最左下的元素
- 若被删除关键字所在节点删除前的关键字个数低于下限，且与次节点右(或左)兄弟节点的关键字个数还很宽裕，则需要调整该节点左右兄弟节点及其双亲
- 若被删除关键字所在节点删除前的关键字个数低于下限，且此时与该节点相邻的左、右兄弟节点关键字个数均=[m/2]-1，则讲兄弟节点及双亲进行合并
B+树
定义和性质
m阶的B+树，满足下列条件
- 每个分支节点最多右m棵子树
- 非叶根节点至少有两棵子树，其他每个分支节点至少有[m/2]棵子树(所有子树高度要相同)
- 节点的子树个数与关键字个数相等
- 所有叶节点包含全部关键字及指向相应记录的指针，叶节点中将关键字大小按顺序排列，并且相邻叶节点按大小顺序相互链接起来
- 所有分支节点中仅包含它的各个子节点中关键字的最大值及指向其子节点的指针
查找
无论查找成功与否，都要走到最下面一层，因为只有叶子节点才有关键字对应的记录
B+树和B树的区别
- 在B+树中，非叶节点不含邮该关键字对应记录的存储地址
- 可以使一个磁盘块可以包含更多关键字，使得B+树的阶更大，树高也更矮，读盘次数更少，查询更快
- MySQL的索引就是B+树
散列(哈希)查找
定义
- 散列表，又称哈希表
- 特点是：数据元素的关键字与其存储地址直接相关
- 通过哈希函数建立关键字和存储地址的联系
- 若不同的关键字通过散列函数映射到同一个值，则称他们为同义词
- 通过散列函数确定的位置已经存放了其他元素，则称他们为冲突
处理冲突方法有：拉链法、开放定址法、再散列法
处理冲突的方法-拉链法(链地址法)
- 拉链法，又称链接法、链地址法
- 操作：把所有同义词存储在一个链表中
- 冲突越多，查找效率越低
- 实际上就是顺序表和链表的结合，用顺序表随机存储，用链表解决冲突
- 插入新元素时，保持关键字有序，可以稍微提高查找效率
处理冲突的方法-开放定址法
- 开放定址法：可存放新表项的空闲地址既向它的同义词表开放，又向它的非同义词项开放
- 递推公式为 $H_i = (H(key) + d_i) % m$, m表示表长，$d_i$为增量序列，i可以理解为第i次发生冲突
开放定址法又分为线性探测法、平方探测法和伪随机序列法
线性探测法
- 发生冲突时，每次往后探测相邻的下一个单元是否为空，为空则直接插入数值
- 查找也是类似，先通过公式的到$H_i$再依次往后查找，如果遇到空的位置，则说明查找失败，所以越早遇到空的位置就可以越早确定失败
- 删除节点不能简单将被删除节点置为空，否则将阶段在它之后填入散列表的同义词节点查找路径，可以做一个删除标记，进行逻辑删除
- 线性探测法犹豫冲突后再探测一定是放在某个连续的位置，容易造成同义词，非同义词堆积现象
平方探测法
- 比起线性探测法，更不容易产生对接问题
- 注意负数的模运算
- 散列表长度m必须是一个可以表示成4j + 3的素数，才能探测到所有位置
伪随机序列法
- $d_i$是一个伪随机序列，如$d_i$=0,5,…
处理冲突的方法-再散列法
- 除了原始的散列函数H(key)之外，多准备几个散列函数
- 当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止
常见的散列函数
设计目的
- 让不同的关键字尽可能少冲突
保留余数法
H(key) = key % p
- 散列表长为m，取一个不大于m但接近或等于m的质数p
- 用质数取模，分布更均匀，冲突更少
直接定址法
H(key) = key 或 H(key) = a * key + b
- 这种方法最简单，且不会产生冲突。但容易空间浪费
- 适合分布基本连续的情况
数字分析法
选取数码分布较为均匀的若干位作为散列地址
- 设关键字是r进制数，而r个数码在各位上出现的频率不一定相同
- 可选取数码分布较为均匀的若干位作为散列地址
- 适合于已知的关键字集合
平方取中法
取关键字的平方值的中间几位作为散列地址
- 具体取多少要实际情况而定
- 散列地址与关键字每位都有关系，因此分布比较均匀
- 适用于关键字每位取值都不够均匀