一、数据查找相干定义
数据查找是依据查问要求从一个计算机文件或数据库中提取所须要的数据的技术。如果要查找的数据全副放在计算机内存储器中，这种查找即称为内查找；若要查找的数据不在内存而在外存储器中，这种查找便称为外查找。
数据个别依照数据项、记录、文件三级组织在肯定的构造之中。用于组织文件的根本数据项称为关键字。所谓从文件中查找数据是指依据给定的关键字值在文件中找出蕴含该关键字值的记录。对于不同的文件构造和查问要求，须要用不同的查找技术。
在各种数据汇合（包含数组、线性表、树等数据结构）中，数据记录在汇合中的理论地位是随机的，和数据记录的关键字之间不存在确定的关系。因而在数据汇合中查找数据记录时须要进行一系列关键字的比拟。比方在程序查找时，比拟的后果为“=”与“!= “ 两种可能。在折半查找、二叉排序树查找和树查找时，比拟的后果为“>”、“<“与“=“三种可能。
查找算法大多数是建设在关键字比拟的根底上。查找的效率次要决定于查找过程中所进行的比拟次数和时长。在等同关键字模式下，以比拟次数为最次要的因素。（比拟树）
最现实的查找算法是不通过任何比拟，一次操作便能失去所查的数据记录。那就必须在数据记录的理论地位和它的关键字之间建设一个惟一确定的对应关系，使每个关键字和数据汇合中某个惟一的理论地位绝对应。
数据查找三种实现形式：
（1）比拟树，须要屡次关键字的比拟，能力找到数值；
（2）哈希表：数据记录地位与关键字处分了对应关系。一次计算就能找到数值，须要一次关键字比拟确认找到的是正确的关键字；
（3）前缀树：只须要一次关键字的比拟，将关键字拆分成多个局部，别离进行比拟；
二、比拟树
算法的比拟树（也被叫作决定树或查找树），取得的办法是，追踪算法行为，用树节点（咱们用画圈来示意）来描述每次键（关键字、key）比拟。圈里咱们搁置用来与指标键做比拟的那些键的索引。树枝（线）由圈的地位向下画，示意比拟的后果，而后像前边一样被标记上。
比拟树，个别应用的都是数字，不是字符串。将整个 key 进行原子化比拟。
2.1 BST
二叉搜寻树（BST）又称二叉查找树或二叉排序树。
（1）一棵二叉搜寻树是以二叉树来组织的，能够应用一个链表数据结构来示意，其中每一个结点就是一个对象。个别地，除了 key 和地位数据之外，每个结点还蕴含属性 lchild、rchild 和 parent，别离指向结点的左孩子、右孩子和双亲（父结点）。
（2）如果某个孩子结点或父结点不存在，则相应属性的值为空（NIL）。根结点是树中惟一父指针为 NULL 的结点，而叶子结点的孩子结点指针也为 NULL。
BST 的每个数据项都有各自的关键字（key），并以此与其余的数据项辨别。查找某数据项就相当于查找其关键字。这样的拜访形式有前提条件，即关键码要反对大小比拟与相等比对。
2.2 AVL
AVL 树是最先创造的自均衡二叉查找树。在 AVL 树中任何节点的两个子树的高度最大差异为 1，所以它也被称为高度均衡树。AVL 树实质上还是一棵二叉搜寻树，它的特点是：
（1）自身首先是一棵二叉搜寻树。
（2）带有平衡条件：每个结点的左右子树的高度之差的绝对值（均衡因子）最多为 1。
也就是说，AVL 树，实质上是带了均衡性能的二叉查找树（二叉排序树，二叉搜寻树）。通过左旋和右旋算法调整树结构。
2.3 红黑树
红黑树（Red Black Tree）是一种自均衡二叉查找树。在进行插入和删除操作时通过特定操作放弃二叉查找树的均衡，从而取得较高的查找性能。
红黑树是一种均衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的均衡二叉树（AVL），但进行均衡的代价较低，其均匀统计性能要强于 AVL。
红黑树利用于 C ++ STL 中 容器 map，set 底层以及 linux 任务调度、虚拟内存等。
红黑树是近似均衡的二叉查找树，它含有以下个性：
（1）每个节点要么是红色，要么是彩色；
（2）根节点必须是彩色；
（3）红色节点不能间断（也即是，红色节点的孩子和父亲都不能是红色）；
（4）对于每个节点，从该点至 null（树尾端）的任何门路，都含有雷同个数的彩色节点；
（5）每个叶子节点都为彩色；
2.4 跳表
减少了向前指针的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。
跳表是一个随机化的数据结构，本质就是一种能够进行二分查找的有序链表。跳表在原有的有序链表下面减少了多级索引，通过索引来实现疾速查找。跳表不仅能进步搜寻性能，同时也能够进步插入和删除操作的性能。Rocksdb 的 memTable 应用内联跳跃表（Inline Skip List）.
跳表的个性：
（1）最底层蕴含所有的元素；
（2）每个元素插入时随机生成它的 level；
（3）如果一个元素呈现在 level(x)，那么它肯定呈现在 x 以下的 level 中；
（4）每个索引节点有两个指针，一个向下，一个向右；
（5）跳表查问、插入、删除的工夫复杂度为 O(log n)，与均衡二叉树靠近；
（6）范畴遍历性能高
跳表插入、删除、查找元素的工夫复杂度跟红黑树都是一样量级的，工夫复杂度都是 O(logn)，而且跳表有一个个性是红黑树无奈匹敌的 — 范畴扫描。
所以在工业中，跳表也会常常被用到。因为最大高度是初始时确定的，也就是说，索引的数据量须要提前估算进去。
2.5 B- 树
B- 树是一种多路搜寻树。1970 年，R.Bayer 和 E.mccreight 提出了一种实用于 外查找 的树，它是一种均衡的多叉树，称为 B 树（或 B - 树、B_树）。
一棵 m 阶 B 树 (balanced tree of order m) 是一棵均衡的 m 路搜寻树。它或者是空树，或者是满足下列性质的树：
（1）根结点至多有两个子女；
（2）每个非根节点所蕴含的关键字个数 j 满足：┌m/2┐ – 1 <= j <= m – 1；
（3）除根结点以外的所有结点（不包含叶子结点）的度数正好是关键字总数加 1，故外部子树个数 k 满足：┌m/2┐ <= k <= m；
（4）所有的叶子结点都位于同一层。
B- 树的搜寻，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则完结，否则进入查问关键字所属范畴的儿子结点；反复，直到所对应的孩子指针为空，或曾经是叶子结点
2.6 B+ 树
B+ 树是一种树数据结构，是一个 n 叉树，每个节点通常有多个孩子，一棵 B + 树蕴含根节点、外部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个蕴含两个或两个以上孩子节点的节点。
B+ 树是应文件系统所需而出的一种 B - 树的变型树。B+ 树是为磁盘或其余直接存取辅助设施而设计的一种均衡查找树。B+ 树是 B - 树的变体，也是一种多路搜寻树：
B+ 树定义根本与 B - 树同，除了：
（1）非叶子结点的子树指针与关键字个数雷同；
（2）非叶子结点的子树指针 P[i]，指向关键字值属于 [K[i], K[i+1]) 的子树（B- 树是开区间）；
（3）为所有叶子结点减少一个链指针；
（4）所有关键字都在叶子结点呈现；
B+ 树通常用于数据库和操作系统的文件系统中。NTFS, NSS, XFS, JFS 和 BFS 等文件系统都在应用 B + 树作为元数据索引。B+ 树的特点是可能保持数据稳固有序，其插入与批改领有较稳固的对数工夫复杂度。B+ 树元素自底向上插入。
三、哈希表
散列表（Hash table，也叫哈希表），是依据关键字 (Key) 而间接进行拜访的数据结构。通过把关键字映射到表中一个地位来拜访记录，以放慢查找的速度。这个映射函数叫做散列函数，寄存记录的数组叫做散列表。
给定表 M，存在函数 f(key)，对任意给定的关键字 key，代入函数后若能失去蕴含该关键字的记录在表中的地址，则称表 M 为哈希 (Hash）表，函数 f(key) 为哈希(Hash) 函数。
Linux 内核中大量应用了 hash 表。
如果两个不同关键字的 hash Code 雷同（在表中的地址），这种景象称为 hash 抵触。任意长度的消息压缩到固定长度的音讯时的信息失落，是导致 hash 抵触的根本原因。
哈希表内解决哈希抵触的办法：
（1）开发定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）：依据以后地址再计算出一个地址
（2）再哈希法：同时结构多个不同的哈希函数
（3）链地址法：所有哈希地址雷同的放在同一个链表中
（4）建设一个公共溢出区：哈希表分为根本表和溢出表两局部，但凡和根本表发生冲突的元素，一律填入溢出表
哈希抵触过多，意味着：数据 insert/delete 的时候须要 lock 整个抵触链表，同步开销增大。抵触链表过长，造成遍历开销过大。解决抵触的无效方法，就是用更大的 hash 表，对数据进行 rehash。
四、前缀树
trie，又称前缀树或字典树，是一种有序树，用于保留关联数组，其中的键通常是字符串。与二叉查找树不同，键不是间接保留在节点中，而是由节点在树中的地位决定。一个节点的所有子孙都有雷同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。个别状况下，不是所有的节点都有对应的值，只有叶子节点和局部外部节点所对应的键才有相干的值。
它有 3 个根本性质：
（1）根节点不蕴含字符，除根节点外每一个节点都只蕴含一个字符；
（2）从根节点到某一节点，门路上通过的字符连接起来，为该节点对应的关键字；
（3）每个节点的所有子节点蕴含的字符都不雷同。
4.1 基数树
基数树（Radix tree），又称压缩前缀树，是一种更节俭空间的 Trie（前缀树）。所有节点应用固定大小的数组，用于存储 token 的所有值。以二进制位串为关键字的 trie 树，是一种多叉树形构造，同时又相似多层索引表，每个两头节点蕴含指向多个子节点的指针数组，叶子节点蕴含指向理论的对象的指针。
其个性是：
（1）树的高度（复杂度）与记录数量无关，仅与 key 值长度无关
（2）更新和删除不波及到树结构的调整，不同插入程序产生雷同的树
（3）达到叶子节点的门路，示意该节点的 key。
毛病：在 key 值稠密状况下，每个 node 内的空间占用很少，导致内存上的节约，所以 Radix Tree 并没有广泛应用在 DBMS 中。
4.2 ART 树
Adaptive Radix Tree（自适应基数 / 前缀树，ART）可变的基数树，在 Radix tree 的根底上，优化减少可变个性，其外围是优化空间的利用率。每个节点的空间大小不再雷同，而是依据须要应用不同的节点类型。
ART 树针对基数树的优化点有：节点划分不同类型、门路压缩、懒扩大。
五、MassTree
能够了解为 B + Tree 和 Radix Tree 的混合体，行将键切分成多个局部，每个局部为一个节点；每个节点外部又是一个 B+ Tree，兼顾空间和性能。
每个虚线框代表一棵 B+ 树，对于每一层（Layer）的 B+ 树，采纳 8 字节进行索引。长度小于 (8h + 8) 字节的 key 会被寄存在 layer <=h。比方，两个 key 寄存在 layer 1，那么它们的前 8 字节是雷同的。
圆形代表外部节点（interior node，也就是 B+ 树的 branch node），矩形代表边缘节点（border node，也就是 B+ 树的 leaf node），五角星代表 value。border node 的 value 域可能寄存的是数据，也可能寄存的是下一层子树的根节点。
六、哈希树
哈希树（hash tree、Merkle tree），是一种树形数据结构，每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签。哈希树可能高效、平安地验证大型数据结构的内容。
抉择质数分辨算法来建设一棵哈希树。
Root 为哈希树的根（深蓝色节点）。
R0 和 R1 为第一层节点（灰色节点）共有 2 个，对应除数序列中的第一个数。
R00、R01、R02、R10、R11、R12 为第二层节点（黄色节点）共 6 个。其中 R00、R01 和 R02 是属于 R0 的子节点，R10、R11 和 R12 是属于 R1 的子节点。R0 和 R1 下别离有 3 个子节点，对应除数序列中的第二个数。
后续的 R00、R01、R02、R10、R11 和 R12 节点下又别离有 5 个子节点（红色节点），对应除数序列中的第三个数。
从 2 起的间断质数，间断 10 个质数就能够分辨大概 M(10) =23571113171923*29= 6464693230
七、查找算法性能比拟
ART：自适应基数树（The Adaptive Radix Tree）
CSB：一种内存优化后的 B + 树（Cache-Sensitive B +-tree [CSB]）,
kary：每个节点都有 k 维点的树（k-ary search tree）
FAST：对均衡二叉树查问进行了优化（Fast Architecture Sensitive Tree）
GPT：基数树（Generalized Prefix Tree）
• RB：红黑树（red-black tree）,
• HT：哈希表（chained hash table，using MurmurHash).
从下面两个比拟中，能够发现 ART 树领有极好的性能，简直能够匹敌哈希表。ART 树比哈希表的劣势是，反对范畴查找。因而，云溪数据库在存储层应用 ART 树算法进行数据查找。