查找

查找分为内查找和外查找。

顺序表查找：

　线性表的顺序存储结构主要使用两种方法：顺序查找和二分查找。

1）顺序查找：从表的一端开始，顺序扫描线性表，依次把扫描的记录和关键字比较，如果相等查找成功返回所在记录下标，否则失败，继续查找直到扫描完成。

2）二分查找：要求查找线性表必须是顺序存储结构的有序表，首先将关键字和线性表中间位置的记录比较，若相等，查找成功，否则，如果大于关键字，覆盖当前中间位置为，从左边子表查询1-(mid-1),

小于关键字，从右边子表查询（mid+1)-n，循环直到查找完成。

3）索引顺序查找：通过把顺序记录分块存储后保证每一个的最大值在每个分块之间有序进行，分两部查找：先查询某一个块的记录在进行区间内顺序查找指定关键字。

树表的查找：

 1）二叉排序树：

（1）若左子树非空，则左子树所有结点均小于根节点值。

（2）若右子树非空，则右子树所有结点均大于根节点值。

（3）左、右子树本身又是一棵二叉排序树。

 2）B树：一棵m阶的B树中包含以下特定

（1）每个结点包含关键字个数、关键字、指向子树的指针。

（2）树中每个结点至少m棵子树。

（3）若树非空，根结点至少有一个关键字，至多m-1个关键字。

（4）所有叶结点都在同一层，并且不带信息。

（5）每个非根结点所包含关键字个数满足：[m/2]-1<=n<=m-1。

3）B+树：主要用于文件组织结构的变形树。与B树的差异在：

（1）有k个孩子的结点就包含k个关键字。

（2）所有叶结点包含了关键字的信息以及指向相应结点的指针，且叶子结点本身按照关键字大小排序链接。

（3）所有非终端结点可看成索引，结点包含子树中最大或最小的关键字。