排序数据的二分查找
二分查找的时间复杂度是\(O(log_2n)\),明显快于暴力搜索。
索引
建立索引的数据，就是通过事先排好顺序，在查找时可以应用二分查找来提高查询效率。
所以索引应该尽可能建立在主键这样的字段上，因为主键必须唯一，所以这样生成的二叉查找树的效率是最高的。
数据库索引的原理-- B+ 树
数据库用 B+ 树来实现索引
其中， 非叶子节点形如
\(<P_1,K_1,P_2,K_2,...,P_{c-1},K_{c-1},P_c>\)
以第一层为例，\(<P_1,59,P_2,97,P_3>\).满足数据部分（\(K_i\))从小到大有序排列，且指针\(P_i\)指向的下一个节点\(X\)满足\(K_{i-1}<X<=K_i\) , 例如图中的树，59在它左边节点指向的树里，44在它左边结点指向的树里，15在它左边结点指向的树里，且都是在最右边的位置。
B+树延伸
查找操作
以上图查找\(key=59\)为例，
先访问根节点\([59,97]\), 发现\(key\)小于等于根节点中的第一个数\(59\), 于是继续访问\(59\)左边的指针指向的节点\([15,44,59]\), 发现\(key\)小于等于第三个树\(59\), 于是访问\(59\)左边的指针指向的叶子节点\([51,59]\), 遍历找到要查找的元素\(59\).
叶子节点的详细结构如下图
由于数据指针只在叶子节点上，所以 B+ 树所有查询所有关键字的磁盘 \(I/O\) 的次数都是树的高度。
区间查找
在上面的叶子节点图中，我们可以看到每个叶子节点有一个指针\(P_{next}\), 它的作用体现在区间查找的时候。
例如，需要查询\([21,63]\)之间的关键字。
- \(21<59\)，访问\(59\)左边指针指向的节点\([15,44,59]\).
- \(15<21<44\), 访问\(44\)左边指针指向的叶子节点\([21,37,44]\).
- 遍历这个叶子节点找到\(21\)，下面的操作就如同单链表的遍历，一直遍历到\(63\)即可.
插入操作
不细说了，这篇文章的动图能说明一切知乎文章
只把动图贴到这里
没有超出叶子结点的最大容量m
超出m，要分裂叶子节点
分裂叶子节点导致上层的节点也超出m,要分裂上层的节点
插入数值比当前最大值还大，要保证新的最大值在根节点中，需要重新调整 B+ 树
B+ 树的复杂度
查找、插入和删除等操作的时间复杂度都是\(O(logn)\)
至于这个结论怎么得出的，还是看那篇知乎文章吧，写得太好了。