sql索引为什么不能用二分查找？

Question

学过sql都知道，sql的索引创建默认底层是用b+数的，它的查找效率确实很高，但也额外占用了一点内存，但我想如果创建一个表时，不是有一个主键id吗？能不能通过id进行二分查找效率也和b+数差不多，而且占用的内存不是比较少吗？然后添加内容时可以直接把索引增加放到下面就好了，然后修改数据主键id也不变，删除时也可以不变（因为二分查找只需有序），这个可能实现吗？

Answer 1

引自免费微信小程序：皆我百晓生

在SQL数据库中，使用B+树作为索引结构的原因有多个方面，而二分查找虽然在某些情况下可以提高效率，但在实际应用中并不适合用于构建整个索引系统。

1. 随机访问：B+树设计的主要目标之一是为了支持随机访问。在磁盘存储环境下，读取连续的数据块比跳转到不同的位置要快得多。B+树将所有的数据都存储在叶子节点上，并且这些叶子节点按照键值顺序链接在一起形成一个双向链表，这样就可以快速地定位到特定的记录。相比之下，二分查找通常要求数据已经完全排序，对于磁盘I/O来说，这会导致频繁的随机读取，性能较低。

2. 内存缓存优化：B+树的另一个优点是它能更好地利用内存。由于每个内部节点只存储键值信息，而不包含完整的记录，因此单个内部节点可以容纳更多的键值对，减少了树的高度。这意味着在内存中加载一个B+树的分支时，可以获取更多相关的信息，提高了查询效率。而二分查找则需要逐级查找，每次只能获取一对相邻元素，可能导致更多的内存开销。

3. 范围查询：B+树非常适合执行范围查询。例如，在WHERE子句中使用BETWEEN操作符时，可以通过遍历叶子节点链表来一次性返回所有符合条件的记录。而二分查找更适合于单个元素的查找，处理范围查询时需要重新开始搜索，效率较低。

4. 插入和删除的效率：B+树的设计使得插入和删除操作相对高效。插入和删除节点时只需要调整少量的指针，不需要像二叉查找树那样可能需要重新平衡整棵树。在B+树中，即使在最坏的情况下，插入和删除的时间复杂度也是O(log n)，而二分查找树可能会退化为线性时间复杂度。

5. 主键ID作为唯一标识：尽管主键ID提供了顺序，但这并不意味着可以简单地使用二分查找。首先，主键ID并不是唯一的排序依据，如果存在重复的主键，那么二分查找就无法确定具体的记录。其次，主键ID的分配并不总是连续的，当有大量删除操作后，可能出现空洞，导致二分查找失效。

综上所述，虽然理论上可以尝试使用二分查找，但考虑到实际的数据库应用场景、硬件特性以及查询需求，B+树是一种更为合适的选择。在大多数情况下，它提供了更好的性能和更灵活的操作支持。如果你的应用场景对内存使用非常敏感，或者对特定查询模式有特殊需求，那么可能需要考虑其他数据结构，但这通常是数据库设计和实现层面的问题，而不是用户在编写SQL查询时需要关注的细节。在标准的关系型数据库中，使用B+树作为索引结构已经是经过广泛实践验证的最佳选择。