数据结构中的“查找”（检索）

内查找和外查找：都在内存中查找即内查找，外查找还涉及外存，比如硬盘等。

分类包括：

1、线性表的查找

又分顺序查找、二分查找和分块查找。

1）二分查找又叫折半查找

• 折半查找要求线性表有序。
• 有序是指存在某个关键字的序列。
• 基本思想是拆半。
• 二分查找可以用二叉树来描述，按照二分查找的思想建立一棵二叉树，此树称为二分查找的“判定树”。
• 二分查找的最坏性能和平均性能相近。

2）分块查找

线性表分成块，每块内部不要求有序，但块块之间应有序

2、树表查找

1）二叉排序树

• 左子树非空，则左树上所有节点均小于根。
• 右子树非空，则右树上的所有节点均大于根。
• 左右子树分别仍是二叉排序树
• 二叉排序树中的“中序遍历”是递增序列。
• 同一序列，构成的二叉排序树可能不同。

2）平衡的二叉排序树

• 要求二叉排序树的左子树和右子树的高度最多相差1
• 这个差被成为平衡因子
• 平衡二叉树避免了顺序查找行为的出现。

3）B树

前面方法都只适用于内查找，B树则适合外查找。

B－树是平衡二叉树的一种。

定义一个m阶的B树

• 每个节点至多有m个孩子
• 根节点有两个孩子或者为空
• 每个节点至少有（m/2的上限）个孩子（除了根和叶）。
• 叶在同一层，且叶中没有关键信息。
• 有K个孩子的非叶节点恰好有k-1个关键字。

查找B树时，给定关键字的查找首先从根开始，一定能确定要找的K在Ki和Ki+1之间。在这之间重复寻找，直到成功或者返回指针为空。

文件系统NTFS对目录索引的管理使用B树。