别再问我什么是B+树 了

每当我们执行某个 SQL 发现很慢时，都会下意识地反应是否加了索引，那么大家是否有想过加了索引为啥会使数据查找更快呢，索引的底层一般又是用什么结构存储的呢，相信大家看了标题已经有答案了，没错!B+树!那么它相对于一般的链表，哈希等有何不同，为何多数存储引擎都选择使用它呢，今天我就来揭开 B+ 树的面纱，相信看了此文，B+ 树不再神秘，对你理解以下高频面试题会大有帮助!

• 为啥索引常用 B+ 树作为底层的数据结构
• 除了 B+ 树索引，你还知道什么索引
• 为啥推荐自增 id 作为主键，自建主键不行吗
• 什么是页分裂，页合并
• 怎么根据索引查找行记录

本文将会从以下几个方面来讲解 B+ 树

• 定义问题
• 几种常见的数据结构对比
• 页分裂与页合并

定义问题

要知道索引底层为啥使用 B+ 树，得看它解决了什么问题，我们可以想想，日常我们用到的比较多的 SQL 有哪些呢。

假设我们有一张以下的用户表：

 

1. 根据某个值精确快速查找
2. 根据区间值的上下限来快速查找此区间的数据
3. 索引值需要排好序，并支持快速顺序查找和逆序查找

接下来我们以主键索引(id 索引)为例来看看如何用相应的数据结构来构造它

几种常见的数据结构对比

接下来我们想想有哪些数据结构满足以上的条件

1、散列表

散列表(也称哈希表)是根据关键码值(Key value)而直接进行访问的数据结构，它让码值经过哈希函数的转换映射到散列表对应的位置上，查找效率非常高。哈希索引就是基于散列表实现的，假设我们对名字建立了哈希索引，则查找过程如下图所示：


 

（编辑：鹤壁站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!