「SQL」拜托，别再问我什么是 B+ 树了 |数据结构|

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

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

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

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

本文插图
定义问题要知道索引底层为啥使用 B+ 树，得看它解决了什么问题，我们可以想想，日常我们用到的比较多的 SQL 有哪些呢。
假设我们有一张以下的用户表：
CREATE TABLE `user` (`id` int(11) unsigned NOT AUTO_INCREMENT,`name` varchar(20) DEFAULT COMMENT '姓名',`idcard` varchar(20) DEFAULT COMMENT '身份证号码',`age` tinyint(10) DEFAULT COMMENT '年龄',PRIMARY KEY (`id`)) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='用户信息'; 一般我们会有如下需求：
1、根据用户 id 查用户信息
select * from user where id = 123;
2、根据区间值来查找用户信息
select * from user where id > 123 and id < 234;
3、按 id 逆序排列，分页取出用户信息
select * from user where id < 1234 order by id desc limit 10;
从以上的几个常用 SQL 我们可以看到索引所用的数据结构必须满足以下三个条件

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

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

本文插图
【「SQL」拜托，别再问我什么是 B+ 树了】
几种常见的数据结构对比接下来我们想想有哪些数据结构满足以上的条件
1、散列表
散列表（也称哈希表）是根据关键码值(Key value)而直接进行访问的数据结构，它让码值经过哈希函数的转换映射到散列表对应的位置上，查找效率非常高。哈希索引就是基于散列表实现的，假设我们对名字建立了哈希索引，则查找过程如下图所示：

本文插图
对于每一行数据，存储引擎都会对所有的索引列（上图中的 name 列）计算一个哈希码（上图散列表的位置），散列表里的每个元素指向数据行的指针，由于索引自身只存储对应的哈希值，所以索引的结构十分紧凑，这让哈希索引查找速度非常快！但是哈希索引也有它的劣势，如下：

针对哈希索引，只有精确匹配索引所有列的查询才有效，比如我在列（A,B）上建立了哈希索引，如果只查询数据列 A ，则无法使用该索引。
- 上一页
- 1
- 2
- 3
- 4
- 5
- 下一页