第八章 查找

查找表按操作方式可以分为：
静态查找表（Static Search Table）：只作查找操作的查找表。它的主要操作有：
（1）查询某个“特定的”数据元素是否在查找表中。
（2）检索某个“特定的”数据元素和各种属性。
动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。显然动态查找表的操作就是两个：
（1）查找时插入数据元素
（2）查找时删除数据元素
面向查找操作设置的数据结构：查找结构
8.3顺序表查找
优化：添加哨兵
8.4有序表查找
二分查找
要求：顺序存储，关键字有序
[log2n] + 1
复杂度：O(logn)
插值查找，二分查找的改进，为什么一定是二分，不是4分，8分呢？
核心在于插值的计算公式：
(key-a[low])/(a[high]-a[low])
斐波那契查找
8.5线性索引查找
索引按照结构可以分为线性索引、树形索引和多级索引。我们这里就只介绍线性索引技术。
所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。
我们重点介绍三种线性索引：稠密索引、分块索引和倒排索引。
稠密索引:稠密索引的索引表，索引项一定要按照关键码有序排列
索引项和数据集的记录个数相同
分块索引：块内无序、块间有序
索引项结构：最大关键码、记录个数、指向首元素的指针
平均查找长度ASLw,最佳。让分的块数和块中记录t相同。n^0.5+1，好于顺序查找O(n)；与二分查找O(logn)还有差距
倒排索引：
inverted index
有没有一种结构，插入和删除效率不错，同时又可以高效率地实现查找呢？—动态查找树
8.6二叉排序树 BST Binary Sort Tree
若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。
从二叉排序树的定义也可以知道，它前提是二叉树，然后它采用了递归的定义方法，再者，它的结点间满足一定的次序关系，左子树结点一定比其双亲结点小，右子树结点一定比其双亲结点大。
构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度
二叉树的最差情况—>一个斜树，查找时间复杂度是O（n），等于顺序查找
—>希望二叉树两边平衡一点，斜树是不平衡的极端例子—>平衡二叉树
二叉排序树的查找、插入、删除操作
8.7平衡二叉树-AVL树
一种二叉排序树，其中每一个左右子树的高度差至多等于1
首先是一个二叉排序树
平衡因子BF(左子树深度减去右子树深度)，只可能是 -1 0 1
最小不平衡子树
8.8多路查找树(B树)
—为了降低对外存设备的访问次数
从B树、B+树、B树谈到R 树
因为磁盘的操作费时费资源，如果过于频繁的多次查找势必效率低下。那么如何提高效率，即如何避免磁盘过于频繁的多次查找呢？
根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构尽量减少树的高度，那么是不是便能有效减少磁盘查找存取的次数呢？那这种有效的树结构是一种怎样的树呢？
这样我们就提出了一个新的查找树结构——多路查找树
后面，我们将看到，B树的各种操作能使B树保持较低的高度，从而达到有效避免磁盘过于频繁的查找存取操作，从而有效提高查找效率
要么有孩子，要么一个孩子也没有
2-3树 一个节点最多两个节点，接三个子树 —>3阶B树
2-3-4树 一个节点最多三个节点，接三=四个子树 —>4阶B树
这些都是B树的特例。
节点最大的孩子数目，称为B树的阶

问：为什么 除根节点和叶节点外，其他每个节点至少有ceil(m/2)个孩子（ceil()为向上取整）？
答：一半的限制一是为了保证存储密度，二是避免树结构退化，保证其在磁盘存储器中的存储优势。
B树：有限的内存下，每一次磁盘访问可以获得最大数据量的数据。方便了内外存的数据交换
B+树：是应文件系统所需而产生的一种B-tree的变形树。严格意义上讲，他已经不是第六章定义的树了
B树：遍历性能很差
.
为什么说B+tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？
数据库索引采用B+树的主要原因是， B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）
B+树的结构，特别适合带范围的查找
B树、B-树、B+树、B树 该文有误，这里的B树就是BST二叉排序树，B-树才是B树
B-tree/B+tree/B*tree
http://blog.jobbole.com/24006/
MySQL索引背后的数据结构及算法原理
局部性原理；一个数据被用到时，其附近的数据也通常会马上被使用。
程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页的大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行
数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
查找（一）史上最简单清晰的红黑树讲解
红黑树(一)之 原理和算法详细介绍
二叉查找树和快速排序几乎就是“双胞胎”
树的根结点就是快速排序中的第一个切分元素（左侧的键都比它小，右侧的键都比它大），而这对于所有的子树同样适用，这和快速排序中对于子数组的递归排序完全对应—>
2-3树的插入：
先找插入结点，若结点有空(即2-结点)，则直接插入。如结点没空(即3-结点)，则插入使其临时容纳这个元素，然后分裂此结点，把中间元素移到其父结点中。对父结点亦如此处理。（中键一直往上移，直到找到空位，在此过程中没有空位就先搞个临时的，再分裂。
2-3树的总结
优点
2-3树在最坏情况下仍有较好的性能。每个操作中处理每个结点的时间都不会超过一个很小的常数，且这两个操作都只会访问一条路径上的结点，所以任何查找或者插入的成本都肯定不会超过对数级别。
完美平衡的2-3树要平展的多。例如，含有10亿个结点的一颗2-3树的高度仅在19到30之间。我们最多只需要访问30个结点就能在10亿个键中进行任意查找和插入操作。
缺点
我们需要维护两种不同类型的结点，查找和插入操作的实现需要大量的代码，而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。
平衡一棵树的初衷是为了消除最坏情况，但我们希望这种保障所需的代码能够越少越好。
红黑树
理解红黑树一句话就够了：红黑树就是用红链接表示3-结点的2-3树。那么红黑树的插入、构造就可转化为2-3树的问题，即：在脑中用2-3树来操作，得到结果，再把结果中的3-结点转化为红链接即可。
红黑树的定义是满足下列条件的二叉查找树：
⑴红链接均为左链接。
⑵没有任何一个结点同时和两条红链接相连。
⑶该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
注意：
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高
8.9散列表查找
存储位置 = f （关键字）
这种对应关系f，称之为散列函数，又称之为哈希函数
散列的记录之间不存在什么逻辑关系(与线性表、树、图不同）
散列是面向查找的存储结构
散列技术最合适的求解问题：查找与给定值相等的记录
散列：不适合范围查找
精心设计散列函数，避免冲突
直接定址法 线性函数 ax+b
数字分析法 抽取
平方取中法
折叠法
除留余数法 最常用
随机数法
处理散列冲突的方法
堆积 P362
1开放定址法：线性探测法、二次探测法、随记探测法
fi(key) = (f(key)+di) MOD m (di是一个随机数列)
2再散列函数法
3链地址法 每多一个冲突，就往链表后面多加一个元素
4公共溢出区法
解决Hash冲突的几种方法
散列表查找性能分析：
如果没有冲突，散列查找是本章中查找效率最高的。但是这只是理想情况，在实际中，冲突是不可避免的。
装填因子α
选择一个合适的装填因子，将查找的平均查找长度限定在一个范围内，
即把散列表的空间设置为比查找集更大
顺序表查找
有序表查找
线性索引查找 —稠密索引、分块索引、倒排索引
二叉排序树 —平衡二叉树—兼顾查找效率，让插入和删除效率也很高
多路查找树(B树) —针对内外存之间的存取
散列表 —散列函数的选择、如何处理冲突
散列表回避了关键字之间反复比较的繁琐，而是一步到位找到结果。当然这也带来了记录之间没有任何关联的弊端