索引算法介绍

线性查找

线性查找就是最简单的查找算法，在一个数组或者链表从头到尾遍历查找，时间复杂度是o(n)

二分查找

二分法.gif

二分法相比于线性查找时间复杂度降低到了o(logn)级别，但是添加了一些限制

• 必须是数组，支持随机访问
• 数组中元素必须是有序的

二叉搜索树

二分搜索树.png

二分法的缺点就是必须支持随机访问，但是对于数组而言如果进行插入操作的话时间复杂度是o(n)级别；二分搜索树就是结合了二分法和链表的优势实现的，二分搜索树有如下特点

• 二分搜索树是满二叉树
• 二分搜索树中任一节点大于左子树的所有节点、小于右子树的所有节点
• 搜索、插入、删除的时间复杂度是o(logn)级别的

平衡搜索树

平衡二叉树本质上还是二分搜索树，只不过平衡二叉树约束了左子树和右子树的高度，比如红黑树要求任意节点左右子树的高度差不能超过1

二分搜索树在左右子树极不平衡的情况下会退化成链表，平衡二叉树就是为了解决此问题的

B树

平衡二叉树有两个问题：

• 平衡二叉树一个节点只能存储一个数据

  在内存中这样并没有问题，但是在数据库场景下落盘就会存在问题：硬盘读取的最小单位是扇区，可能是512字节或者4KB；假设我们读取一个节点，那么从硬盘中一次读取的数据只有很少一部分有用

• 平衡二叉树深度较高

  平衡二叉树很容易达到几十层，对于硬盘IO来说代价还是有点大

B树.png

B树是类似于图中这样的树，它是结合了线性查找和二分搜索树的特点而来的：

• 每一个节点可以存储多项内容，每一项同时包含索引和数据

备注：普通的二叉树或B树每个节点存储的就是整数，这个整数既是节点的数据也是节点用来索引/排序的标记；但是在真正的场景中如MySQL中，一项数据包括很多内容而索引可能只是其中一项。

B+树

B树同样存在问题，就是在范围查找时非常困难

B+树.png

B+树和B树的区别在于

• 底层是一个双向链表，存储了所有的数据
• 上层只存储索引而不存储数据