数据库索引底层为什么采用B+树

一、前言

需求：
从查询角度考虑，数据库查询一般有单值查询和范围快速查询的需求。
比如：
根据某个具体的值快速查询，select * from users where id=999;
查询某个范围的数据：select * from users where id>100 and id<200;

除此之外，存储空间方面也希望不要消耗太多空间。

对于常用的数据结构来说，散列表支持快速查询某个具体的值，时间复杂度O(1)，但是散列表不支持范围快速查找；
二叉查找树查找某个具体的值的时间复杂度可以达到O(logn)，但是也不支持范围查找；有序链表支持范围查询，但查询效率较低。

二、B+树

1. B+树是一种多叉树，在二叉查找树的基础上改进的一种数据结构；
2. 对于m叉树来说，每个节点的孩子节点不超过m,也不能小于m/2;
3. B+树的非叶子节点只存储索引，是有序的，叶子节点存储的是真正的数据；
4. 通过双向链表将叶子节点串联起来，也是有序的，便于按区间快速查找；
5. 通常情况下，根节点存储在内存中，其他节点存储在磁盘中，有效降低了内存消耗；
6. 每个节点的读取（或者访问），都对应一次磁盘IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数，所以说要尽可能降低书的高度，采用多叉树也是w为了降低树的高度。