二分搜索法二分搜索法(binary search )也称为折半搜索法，用于在规则的记录数组中查找某个记录。 简而言之，按照有序化)排列记录，在搜索中进行跳跃式搜索。 也就是说，首先以规则数组的中间位置作为比较对象，如果要搜索的要素的值小于其中间要素，则将搜索对象向左半部分缩小，否则向左半部分缩小。通过一次比较，搜索区间将缩小一半。 具体情况如下。
这里有10个数字。 现在，我需要找48这个记录。 二分法的检索过程到此结束。 最初的检索37、48大于37，所以在右侧再次用二分法调查。 这次定位为大于50的48，在左侧调查的话，可以得到48。 整个过程被调查了三次。 但是，使用顺序检索方式需要7次。 但是，如果要调查的数据是5的话，顺序方式只需要1次即可，二分法需要4次。 但实际上二分法查找效率高于逐次查找，对上面10个数字来说，逐次查找的平均次数为(1 2 3 4 5 6 7 8 9 10 )/10=5.5次。 使用二分法进行的检索为(432431433 )/10=2.9次。 在效率最低的情况下，依次检索只需要10次，二分法只需要4次。 使用Innodb存储引擎二分法应用于每页Page Directory的插槽按主键顺序存储，并且通过二分法搜索Page Directory可以获得对特定记录的查询。
二叉搜索树和平衡二叉树b树由二叉搜索树、平衡二叉树、b树演化而来。
图为两条腿找树：
上图中的每个节点表示每个节点的键值。 在双击树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值因此可以通过中顺序扫描获得键值排序输出，上图中的二叉搜索树经过中顺序扫描输出： 2、3、5、6、7、8。 对于这棵树的检索，如果现在需要找5这个记录，检索过程如下。 首先找到路线，其键值为6，6 & gt； 5，所以你需要找到6左边的子树，找到3。 小于3的情况下找右边的子树，一共找了三次。 我也会查三次按顺序找的方法。 如果要搜索的记录为8，则也需要3次，但依次搜索将搜索6次。 计算平均查找次数，依次查找的平均查找次数为(1 2 3 4 5 6 )/6=3.3次； 二叉树的平均搜索次数为[33321]/6=2.3次，因此二叉树比逐次搜索还要快。
二叉查找树可以随意构造，同样数字也可以如下构成
该树的平均搜索次数为[12345]/6=3.16次，与顺序搜索基本相同，该树的效率比上述效率稍低。 因此，为了制作最大性能的二叉树，这个二叉树是平衡的，需要出现新的定义——平衡二叉树，或者称为AVL树。
平衡二叉树的定义如下。
首先，需要满足二叉树的定义，其次需要满足任意节点的两个子树的高度的最大差是1。 所以上面的二叉树不符合这个要求。 二叉树的搜索性能平衡比较高，但不是最高的。 优化性能需要建立最优二叉树，而最优二叉树的建立和维护需要大量的维护工作，因此用户往往只需要建立均衡的二叉树。
平衡二叉树的查询速度确实很快，但维护一棵二叉树的成本非常高，通常需要一次或多次左转或右转来平衡插入或更新的树。 以下两种情况：
除了插入操作之外，还有更新和删除操作，这与插入没有本质上的区别，可以左旋或右旋进行。 因此，保持平衡的二叉树虽然有开销，但是二叉树在内存中被广泛使用，虽然有一定的开销，但是对数据库的影响很小。
树b是为磁盘或其他直接访问附件设计的平衡查找树，所有记录的节点按键值大小顺序存储在同一层次的叶节点中，并按顺序存储。 当用户从最左边的叶节点开始按顺序遍历时，将获得所有键值的顺序。 五、十、十五、二十、二十五、三十、五十、五十五、六十
B树的插入操作B树的插入，既要保证在插入后叶节点中的记录仍然被排序，又要考虑插入B树的三种情况，根据不同的情况插入算法可能不同。 如下所示。
第一，Leaf Page和Index Page都是完全直接插入即可
此时必须插入密钥值28
第二种情况： Leaf Page已满，但索引page还未满。 分割操作
此时需要插入密钥值70
直接插入的Leaf Page的情况下为50、55、60、65、70，但是由于叶子填满了，基于中位数60分割叶子的节点如下图所示。
第三种情况是Leaf Page和Index Page写得满满的，在这种情况下需要分割两次
此时插入的值是95这个键值
无论如何变化，b树总是保持平衡，但是为了保持平衡，可能需要对新插入的键值进行大量的分割页面(split )操作。 B树的结构主要用于磁盘，页面的分割意味着磁盘的操作，所以应该尽可能减少页面的分割操作。 因此，b树也提供平衡二叉树的旋转功能。 当Leaf Page已满，但其左右兄弟节点未满时，会发生旋转。 此时，b树并不着急进行分割页面的操作，而是将记录移动到该页面的兄弟节点。 通常是
情况下，左兄弟会首先检查用来做旋转操作。当插入值70的时候，B+树使用旋转的方式就变成下图所示状态，可以减少一次页的拆分操作，同时这棵B+树的高度依然是2
B+树使用填充因子（fill factor）来控制树的删除变化，50%是填充因子可以设置的最小值。（填充因子就是每个页存放多少键值，例如上图中一个页4个键值，那么一个页在设置50%为最小填充因子那么一个页最少也要有两个键值才可以）。B+树的删除操作同样必须保证删除后叶子节点中的记录依然排序，同插入一样，B+树的删除操作同样需要考虑以下三种情况：
以下图为例，当需要删除键值为70这条记录，该记录符合第一种情况，直接删除即可
上图中左侧为未删除之前的状态，现在需要删除70这个键值，该值删除后填充因子仍然满足50%，同时不是Index Page的节点，所以直接删除就可以。
删除键值为25这条记录，该记录符合第一种情况，但是该节点是Index Page中的值因此在删除后，还要吧25的右兄弟节点的28更新到Index Page中。
删除键值为60的情况，删除Leaf Page中键值为60的记录后，Fill Factor小于50%，这时需要做合并操作，同样在删除Index Page中需要做Index Page合并的操作。