摘要

面试时，交流有关mysql索引问题时，发现有些人能够涛涛不绝的说出B+树和B树，平衡二叉树的区别，却说不出B+树和hash索引的区别。这种一看就知道是死记硬背，没有理解索引的本质。本文旨在剖析这背后的原理，欢迎留言探讨

问题

如果对以下问题感到困惑或一知半解，请继续看下去，相信本文一定会对你有帮助

• mysql 索引如何实现
• mysql 索引结构B+树与hash有何区别。分别适用于什么场景
• 数据库的索引还能有其他实现吗
• redis跳表是如何实现的
• 跳表和B+树，LSM树有和区别呢

解析

首先为什么要把mysql索引和redis跳表放在一起讨论呢，因为他们解决的都是同一种问题，用于解决数据集合的查找问题，即根据指定的key，快速查到它所在的位置（或者对应的value）

当你站在这个角度去思考问题时，还会不知道B+树索引和hash索引的区别吗

数据集合的查找问题

现在我们将问题领域边界划分清楚了，就是为了解决数据集合的查找问题。这一块需要考虑哪些问题呢

1. 需要支持哪些查找方式，单key/多key/范围查找，
2. 插入/删除效率
3. 查找效率（即时间复杂度）
4. 存储大小（空间复杂度）

我们看下几种常用的查找结构

hash

hash是key,value形式，通过一个散列函数，能够根据key快速找到value

B+树

B+树是在平衡二叉树基础上演变过来，为什么我们在算法课上没学到B+树和跳表这种结构呢。因为他们都是从工程实践中得到，在理论的基础上进行了妥协。

B+树首先是有序结构，为了不至于树的高度太高，影响查找效率，在叶子节点上存储的不是单个数据，而是一页数据，提高了查找效率，而为了更好的支持范围查询，B+树在叶子节点冗余了非叶子节点数据，为了支持翻页，叶子节点之间通过指针连接。

跳表

跳表是在链表的基础上进行扩展的，为的是实现redis的sorted set数据结构。 level0: 是存储原始数据的，是一个有序链表，每个节点都在链上 level0+: 通过指针串联起节点，是原始数据的一个子集，level等级越高，串联的数据越少，这样可以显著提高查找效率，

总结

数据结构 实现原理 key查询方式 查找效率 存储大小 插入、删除效率 Hash 哈希表 支持单key 接近O(1) 小，除了数据没有额外的存储 O(1) B+树 平衡二叉树扩展而来 单key,范围，分页 O(Log(n) 除了数据，还多了左右指针，以及叶子节点指针 O(Log(n)，需要调整树的结构，算法比较复杂 跳表 有序链表扩展而来 单key，分页 O(Log(n) 除了数据，还多了指针，但是每个节点的指针小于<2,所以比B+树占用空间小 O(Log(n)，只用处理链表，算法比较简单

对LSM结构感兴趣的可以看下cassandra vs mongo (1)存储引擎

cassandra vs mongo (1)存储引擎

概括

存储引擎：

B-Tree

缓存管理

缓存管理的核心在于置换算法，置换算法常见的有FIFO（First In First Out），LRU(Least Recently Used)。关系型数据库在LRU的基础上，进行了改进，主要使用LIRS(Low Inter-reference Recency Set)
将缓存分为两级，第一次采用LRU，最近被使用到的数据会进第一级，如果数据在较短时间内被访问了两次或以上，则成为热点数据，进入第二级。避免了进行全表扫描的时候，可能会将缓存中的大量热点数据替换掉。

LSM

Log-Structured Merge Tree:结构化合并树，核心思想就是不将数据立即从内存中写入到磁盘，而是先保存在内存中，积累了一定量后再刷到磁盘中

LSM VS B-Tree

LSM在B-Tree的基础上为了获取更好的写性能而牺牲了部分的读性能，同时利用其它的实现来弥补读性能，比如boom-filter.

1.写

B树的写入，是首先找到对应的块位置，然后将新数据插入。随着写入越来越多，为了维护B树结构，节点得分裂。这样插入数据的随机写概率就会增大，性能会减弱。

LSM 则是在内存中形成小的排好序的树，然后flush到磁盘的时候不断的做merge.因为写入都是内存写，不写磁盘，所以写会很高效。

2.读

B树从根节点开始二分查询直到叶子节点，每次读取一个节点，如果对应的页面不在内存中，则读取磁盘，缓存数据。

LSM树整个结构不是有序的，所以不知道数据在什么地方，需要从每个小的有序结构中做二分查询，找到了就返回，找不到就继续找下一个有序结构。所以说LSM牺牲了读性能。但是LSM之所以能够作为大规模数据存储系统在于读性能可以通过其他方式来提高，比如读取性能更多的依赖于内存/缓存命中率而不是磁盘读取。

Cassandra

Cassandra是一个写性能优于读性能的NoSql数据库，写性能好一个原因在于选择了LSM存储引擎。

Mongo

MMAPv1

Mongo 3.2以前默认使用MMAPv1存储引擎，是基于B-Tree类型的。

边界(padding)

MMAPv1 存储引擎使用一个叫做”记录分配”的过程来为document存储分配磁盘空间。MongoDB与Cassandra不同的是，需要去更新原有的document。如果原有的document空间不足，则需要将这个document移动到新的位置，更新对应的index。这样就会导致一些不必要的更新，和数据碎片。

为了避免出现上述情况，就有了边界的概念，就是为document预分配空间。但是这样就有可能造成资源的浪费。mongo 按照64M,128M,256M…2G的2的冥次方递增策略预分配，最大2G。在数据量小的情况下问题并不明显，但是当达到2G时，磁盘占用量大的问题就出来了。

同样这一点和关系型数据库也不一样，关系型数据库对于长记录数据会分开存储。

锁

MMAPv1使用collection级别的锁，即一个collecion增，删，改一次只能有一个。在并发操作时，就会造成等待。

WiredTiger

3.2及其以后的默认存储引擎,同样是基于B-Tree的。采用了lock-free,风险指针等并发技术，使得在多核机器上工作的更好。

锁级别为document。并且引入了compression，减少了磁盘占用。

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对的支持。