查找
查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素
顺序查找 O(n)
从表中第一个记录开始，逐个与给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若直到最后一个记录，其关键字和给定值都不相等，则表明表中没有所查记录，查找失败。
二分/折半查找（有序表） O(logn)
先确定待查记录所在的范围，然后逐步缩小范围，直到找到或者找不到记录为止。
插值查找 O(logn)
插值查找和折半查找类似，可以通过比较表中的某项记录，确定查找记录的范围。唯一不同的是，对每次查找的中间点进行了变换，使之更加接近待查找的记录，减少了查找的次数。折半查找的中间点mid = low + (high – low) / 2，插值查找对1/2进行了修正，mid = low + (key – a[low])/(a[high] – a[low]) * (high – low)
斐波那契查找 O(logn)
依然是对查找点的优化，采用Fibonacci数组，找到对于当前长度的有序表的黄金分割点，作为每次的中间值。
对于平均性能，斐波那契查找要优于折半查找，但如果是最坏情况，查找效率低于折半查找。有序表查找是一种针对查找优化的表结构，查找的时间复杂度是O(logn)。但有序表的插入和删除性能是比较差的，插入和删除不能破坏有序表的特性。
线形索引查找
索引是关键词和记录关联的过程，按照结构可以分为线形索引，树形索引和多级索引。线形索引就是将索引项集合组织为线形结构，也称索引表。
稠密索引 O(logn)
稠密索引是关键码有序的，因此可以对索引使用折半、插值、斐波那契等有序表查找算法，大大提高了效率。
优缺点：和有序表类似的是，稠密索引必须要维护索引的有序性。另外如果数据量很大，也要同时维护一个同样规模的索引，可能就需要反复访问磁盘，降低了查找性能。
分块索引 介于O(n)和O(logn)之间
如果对索引进行一次分级呢？对于一级索引下，可能会有多个记录，称之为一个块，块内的记录再获得一个二级的索引。这些块有一个条件，就是块内无序，块间有序。块内无序就是在一级索引内部的记录可以是无序的，只要落在索引的范围内就可以；块间有序就是下一个块所有的关键字都要大于上一个块的最大关键字。因此对于一个块结构来讲，它具有最大关键码，块中的记录个数和指向块首数据的指针
分块索引兼顾了有序和无序的需求，平衡了插入，删除和查找的性能，普遍用于数据库查找技术等
倒排索引
倒排索引主要应用于搜索引擎。基本思想就是将得到的key-value关系进行一个反映射，得到某个value有多少个key指向它。比如查找某个单词出现在哪些文章中，可以先访问文章中的所有单词，建立一个单词的索引，将出现该单词的文章记录到索引中。这样在搜索时直接输入单词，就能得到文章列表。
优缺点：倒排索引的优点是速度快，缺点就是记录不等长，维护比较困难，插入和删除都要做相应的处理。比如删除某个文章，就可能要对所有的单词都进行考察。
二叉排序树
有序表的问题就是如果插入一个较小的记录，就要把比它大的记录依次移动，腾出插入的位置。如果用二叉树来实现呢，只需要让这个较小的记录成为某个结点的左孩子就可以了。为什么是左孩子呢，和二叉排序数的定义有关，简单来说，二叉排序树的中序遍历就是一个有序表。这样插入任何一个记录都不需要改变已经建好的树
查找：
查找某个记录时，从根结点开始，如果查找记录大于该结点的值，就走右子树；如果小于该结点的值，就走左子树。不断向下查找，直到找到该记录，或者到叶子结点的值和查找记录不同，未找到该记录。
插入
插入和查找类似，向下找到最接近它的结点，然后把该记录作为它的左孩子或者右孩子。
删除
删除相对查找和插入来讲复杂一点，主要复杂在如果处理它的子树。删除分为几种情况，如果删除结点是叶子结点，直接把它和二叉排序树断开即可，不影响树上的其他结点。如果删除结点带左子树或者右子树（不同时），那就将它左子树或者右子树的根结点代替它，连接到树上。如果删除结点同时带有左子树和右子树呢？想要对原排序树的破坏最小，最好的办法是找到该结点的前驱或者后继结点，这可以很容易的找到。假设我们这里使用删除结点的前驱结点，要先将前驱结点的值赋给删除结点，如果前驱结点就是删除结点的左孩子（删除结点及其子孙只有左孩子，斜树），就将前驱结点的左子树接到删除结点的左子树上；如果前驱结点是某个结点的右孩子（删除结点及其子孙不只有左孩子），还要将它的左子树接到它父母的右子树上。
时间复杂度
如果二叉排序树是平衡的，那么查找的时间复杂度是O(logn)；如果是不平衡，比如最极端的斜树，那么时间复杂度是O(n)。
优缺点
二叉排序树保留了有序表查找高效的特点，最理想的情况能达到O(logn)的时间复杂度，并且解决了插入和删除记录的问题，能够保证树的整体结构不受影响。缺点就是可能在插入的过程中，二叉排序树不能保持平衡，出现了某一边的树远远大于另一边，降低了查找的效率。后面提到的平衡二叉树解决了这个问题。
平衡二叉树（AVL）
平衡二叉树的出现是为了解决二叉排序树可能出现的不平衡问题。平衡二叉树的概念是树中任何结点的平衡因子只能是-1,0,1，也就左子树和右子树的深度相差最多是1。为了实现这个目的，每次插入记录后，都会检查二叉树是否处在平衡状态，如果不是的话，会进行相应的旋转操作使之平衡。平衡的过程就是从新插入的结点向上查找，如果某个结点的BF=2，就顺时针旋转。最简单的旋转就是对于斜树，直接将BF=2结点的孩子作为新的子树根结点，将BF=2连接到它的右孩子。稍复杂的旋转就是BF=2和它的左孩子有相同的旋转方向，这样将它的左孩子作为新的子数根结点，BF=2连接在新根结点的右子树上，再将新的根结点原来的右孩子连接到BF=2的左子树上。最复杂的旋转就是BF=2和它的左孩子是相反的旋转方向，就要将它的左孩子先进行一次右旋转，再对BF=2作左旋转。同样，如果找到某个结点的BF=-2，做逆时针旋转，旋转的方法和顺时针旋转类似。
时间复杂度
由于平衡二叉树的特性，它的时间复杂度一直是O(logn)。
优缺点
平衡二叉树的优点就在于将不平衡消灭在最初的阶段，保持了很好的查找特性。缺点？比较复杂？
2-3树
其中的每一个节点都具有两个孩子（称为2节点）或者三个孩子（称为3节点）。并且2-3树中所有的叶子都在同一层上。
一个2节点包含一个元素和两个孩子（或者没有孩子）。
一个3节点包含一小一大两个元素和三个孩子（或者没有孩子）
2-3树的插入实现
(1)对于空树，插入一个2节点即可；
(2)插入节点到一个2节点的叶子上。由于本身就只有一个元素，所以只需要将其升级为3节点即可。
(3)插入节点到一个3节点的叶子上。因为3节点本身最大容量，因此需要拆分，且将树中两元素或者插入元素的三者中选择其一向上移动一层。
2-3树的删除实现
(1)所删元素位于一个3节点的叶子节点上，直接删除，不会影响树结构。
(2)所删元素位于一个2节点上，直接删除，破坏树结构
分为四种情况
3）所删元素位于非叶子的分支节点。此时按树中序遍历得到此元素的前驱或后续元素，补位。
2-3-4树
2-3-4树是2-3树的扩展，包括了4节点的使用，一个4节点包含小中大三个元素和四个孩子（或没有孩子）。
2-3-4树插入实现
构建一个数组为{7,1,2,5,6,9,8,4,3}的2-3-4树的过程
2-3-4树删除实现
删除顺序使1,6,3,4,5,2,9
B树
B树（B-树）是一种平衡的多路查找树。2-3树和2-3-4树都是B树的特例。节点最大的孩子数组称为B树的阶（order），因此，2-3树是3阶B树，2-3-4树是4阶B树。
B树的插入和删除和2-3树、2-3-4树类似。
B树的数据结构为内外存的数据交互准备的。当要处理的数据很大时，无法一次全部装入内存。这时对B树调整，使得B树的阶数与硬盘存储的页面大小相匹配。
比如说一棵B树的阶为1001（即1个节点包含1000个关键字），高度为2（从0开始），它可以存储超过10亿个关键字（1001x1001x1000+1001x1000+1000）,
只要让根节点持久的保留在内存中，那么在这颗树上，寻找某一个关键字至多需要两次硬盘的读取即可。
对于n个关键字的m阶B树，最坏情况查找次数计算
第一层至少1个节点，第二层至少2个节点，由于除根节点外每个分支节点至少有⌈m/2⌉棵子树，则第三层至少有2x⌈m/2⌉个节点。。。这样第k+1层至少有2x(⌈m/2⌉)^(k-1),实际上，k+1层的节点就是叶子节点。若m阶B树有n个关键字，那么当你找到叶子节点，其实也就等于查找不成功的节点为n+1，因此
n+1>=2x(⌈m/2⌉)^(k-1),即
k<=logm/2/2+1)
在含有n个关键字的B树上查找时，从根节点到关键字节点的路径上涉及的节点数不超多 logm/2/2+1)
B+树
下图B树，我们要遍历它，假设每个节点都属于硬盘的不同页面，我们为了中序遍历所有的元素，页面2-页面1-页面3-页面1-页面4-页面1-页面5.
而且我们每经过节点遍历时，都会对节点中的元素进行一次遍历，糟糕！有没有可能让遍历时每个元素只访问一次呢？
下图就是B+树，灰色关键字，在根节点出现，在叶子节点中再次列出。
B+树适合随机查找，只不过查到后是索引，不能提供实际记录的访问，还需要到达包含此关键字的终端节点。非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。B+树适合带有范围的查找。B+树插入、删除类似B树。
详细了解B树和B+树
