Search.js

/*
 查找

 数据的组织和查找是大多数应用程序的核心，而查找是所有数据处理中最基本、最常用的操作。特别当查找的对象是一个庞大数量的数据集合中的元素时，查找的方法和效率就显得格外重要。

 本章主要讨论顺序表、有序表、树表和哈希表查找的各种实现方法，以及相应查找方法在等概率情况下的平均查找长度。

 查找的概念

 查找表(Search Table)：相同类型的数据元素(对象)组成的集合，每个元素通常由若干数据项构成。

 关键字(Key)：数据元素中某个(或几个)数据项的值，它可以标识一个数据元素。若关键字能唯一标识一个数据元素，则关键字称为主关键字；将能标识若干个数据元素的关键字称为次关键字。

 查找/检索(Searching)：根据给定的K值，在查找表中确定一个关键字等于给定值的记录或数据元素。
 ◆ 查找表中存在满足条件的记录：查找成功；结果：所查到的记录信息或记录在查找表中的位置。
 ◆ 查找表中不存在满足条件的记录：查找失败。

 查找有两种基本形式：静态查找和动态查找。
 静态查找(Static Search)：在查找时只对数据元素进行查询或检索，查找表称为静态查找表。
 动态查找(Dynamic Search)：在实施查找的同时，插入查找表中不存在的记录，或从查找表中删除已存在的某个记录，查找表称为动态查找表。

 查找的对象是查找表，采用何种查找方法，首先取决于查找表的组织。查找表是记录的集合，而集合中的元素之间是一种完全松散的关系，因此，查找表是一种非常灵活的数据结构，可以用多种方式来存储。

 根据存储结构的不同，查找方法可分为三大类：
 ①  顺序表和链表的查找：将给定的K值与查找表中记录的关键字逐个进行比较， 找到要查找的记录；
 ②  散列表的查找：根据给定的K值直接访问查找表， 从而找到要查找的记录；
 ③  索引查找表的查找：首先根据索引确定待查找记录所在的块 ，然后再从块中找到要查找的记录。

 查找方法评价指标
 查找过程中主要操作是关键字的比较，查找过程中关键字的平均比较次数(平均查找长度ASL：Average Search Length)作为衡量一个查找算法效率高低的标准。

 */



/*
索引查找

索引技术是组织大型数据库的重要技术，索引结构的基本组成是索引表和数据表两部分。
◆  数据表：存储实际的数据记录；
◆ 索引表：存储记录的关键字和记录(存储)地址之间的对照表，每个元素称为一个索引项。

通过索引表可实现对数据表中记录的快速查找。索引表的组织有线性结构和树形结构两种。


顺序索引表

是将索引项按顺序结构组织的线性索引表，而表中索引项一般是按关键字排序的，其特点是：
优点：
◆  可以用折半查找方法快速找到关键字，进而找到数据记录的物理地址，实现数据记录的快速查找；
◆ 提供对变长数据记录的便捷访问；
◆ 插入或删除数据记录时不需要移动记录，但需要对索引表进行维护。
缺点：
◆ 索引表中索引项的数目与数据表中记录数相同，当索引表很大时，检索记录需多次访问外存；
◆ 对索引表的维护代价较高，涉及到大量索引项的移动，不适合于插入和删除操作。

树形索引表

平衡二叉排序树便于动态查找，因此用平衡二叉排序树来组织索引表是一种可行的选择。当用于大型数据库时，所有数据及索引都存储在外存，因此，涉及到内、外存之间频繁的数据交换，这种交换速度的快慢成为制约动态查找的瓶颈。若以二叉树的结点作为内、外存之间数据交换单位，则查找给定关键字时对磁盘平均进行㏒2n次访问是不能容忍的，因此，必须选择一种能尽可能降低磁盘I/O次数的索引组织方式。树结点的大小尽可能地接近页的大小。

R.Bayer和E.Mc Creight在1972年提出了一种多路平衡查找树，称为B-树(其变型体是B+树) 。

1   B-树
B-树主要用于文件系统中，在B-树中，每个结点的大小为一个磁盘页，结点中所包含的关键字及其孩子的数目取决于页的大小。一棵度为m的B-树称为m阶B-树，其定义是：
一棵m阶B-树，或者是空树，或者是满足以下性质的m叉树：
⑴ 根结点或者是叶子，或者至少有两棵子树，至多有m棵子树；
⑵ 除根结点外，所有非终端结点至少有Math.floor(m/2)棵子树，至多有m棵子树；
⑶ 所有叶子结点都在树的同一层上；
⑷ 每个结点应包含如下信息：

(n，A0，K1，A1，K2，A2，… ，Kn，An)
其中Ki(1≤i≤n)是关键字，且Ki<Ki+1 (1≤i≤n-1)；Ai(i=0，1，… ，n)为指向孩子结点的指针，且Ai-1所指向的子树中所有结点的关键字都小于Ki ，Ai所指向的子树中所有结点的关键字都大于Ki ；n是结点中关键字的个数，且Math.ceil(m/2)-1≤n≤m-1，n+1为子树的棵数。
当然，在实际应用中每个结点中还应包含n个指向每个关键字的记录指针.

 2  B_树的查找

 由B_树的定义可知，在其上的查找过程和二叉排序树的查找相似。

 ⑴ 算法思想
 ① 从树的根结点T开始，在T所指向的结点的关键字向量key[1…keynum]中查找给定值K(用折半查找) ：
 若key[i]=K(1≤i≤keynum)，则查找成功，返回结点及关键字位置；否则，转⑵；
 ② 将K与向量key[1…keynum]中的各个分量的值进行比较，以选定查找的子树：
 ◆  若K<key[0]：T=T->ptr[0]；
 ◆ 若key[i]<K<key[i+1](i=0， 1, 2, …keynum-1)：
 T=T->ptr[i]；
 ◆ 若K>key[keynum-1]：T=T->ptr[keynum]；
 转①，直到T是叶子结点且未找到相等的关键字，则查找失败。

 算法分析

 在B_树上的查找有两中基本操作：
 ◆  在B_树上查找结点(查找算法中没有体现)；
 ◆  在结点中查找关键字：在磁盘上找到指针ptr所指向的结点后，将结点信息读入内存后再查找。因此，磁盘上的查找次数(待查找的记录关键字在B_树上的层次数)是决定B_树查找效率的首要因素。

 在含有n个关键字的B_树上进行查找时，从根结点到待查找记录关键字的结点的路径上所涉及的结点数不超过1+ ㏒Math.floor(m/2)((n+1)/2) 。


 B_树的插入

 B_树的生成也是从空树起，逐个插入关键字。插入时不是每插入一个关键字就添加一个叶子结点，而是首先在最低层的某个叶子结点中添加一个关键字，然后有可能“分裂”。

 ⑴ 插入思想
 ① 在B_树的中查找关键字K，若找到，表明关键字已存在，返回；否则，K的查找操作失败于某个叶子结点，转 ②；
 ② 将K插入到该叶子结点中，插入时，若：
 ◆  叶子结点的关键字数<m-1：直接插入；
 ◆ 叶子结点的关键字数=m-1：将结点“分裂” 。

 ⑵ 结点“分裂”方法
 设待“分裂”结点包含信息为：
 (m，A0，K1，A1，K2，A2，… ，Km，Am)，从其中间位置分为两个结点：
 (Math.floor(m/2)-1，A0，K1，A1，… ，K Math.floor(m/2)-1 ，A Math.floorm/2)-1 )
 (m-Math.floor(m/2)，A Math.floor(m/2)，K Math.floor(m/2)+1，A Math.floor(m/2)+1 ，… ，Km，Am )

 并将中间关键字K Math.floor(m/2)插入到p的父结点中，以分裂后的两个结点作为中间关键字K Math.floor(m/2)的两个子结点。
 当将中间关键字K Math.floor(m/2)插入到p的父结点后，父结点也可能不满足m阶B_树的要求(分枝数大于m)，则必须对父结点进行“分裂”，一直进行下去，直到没有父结点或分裂后的父结点满足m阶B_树的要求。
 当根结点分裂时，因没有父结点，则建立一个新的根，B_树增高一层。


 ⑶ 算法实现
 要实现插入，首先必须考虑结点的分裂。设待分裂的结点是p，分裂时先开辟一个新结点，依此将结点p中后半部分的关键字和指针移到新开辟的结点中。分裂之后，而需要插入到父结点中的关键字在p的关键字向量的p->keynum+1位置上。
 */