目录一. 什么是 Hash1.1 Hash 函数1.2 Hash 碰撞1.3 HashMap 的时间复杂度二. AVL树2.1 简单了解AVL树2.2 AVL树的时间复杂度2.3 AVL树的缺点三. B 树四. B 树五. 为什么数据库不采用哈希表存储数据呢六. 为什么数据库不采取B树的结构存储数据呢七. 为什么数据库不采用 AVL 平衡二叉树存储数据呢八. 自适应 Hash 索引本篇文章是深入理解索引B树的基本原理_程序猿ZhangSir的博客-CSDN博客这篇文章的追加部分和补充的知识点没看过也没关系不影响正常理解。一. 什么是 Hash1.1 Hash 函数Hash 本身其实是一个函数又被称为散列函数它可以大幅提高我们对数据的检索效率。因为它是散列的所以在存储数据的时候它也是无序的。Hash 算法是通过某种确定性的算法(例如MD5SHA1SHA2SHA3)将输入转变成输出相同的输入结果永远会得到相同的输出。1.2 Hash 碰撞熟悉Java中 HashMap 的同学应该知道我们在往 Map 集合中存放元素的时候它会先对要往集合中存放的元素的 key 值做一个哈希运算从而确定它要存入的位置。理论上每一个对象都会存放在不同的地方但当存放的对象越来越多时有可能后来添加的元素的 key 值计算得出的结果与之前已经存入的元素的 key 的哈希值相等这种现象就被称为哈希碰撞。当产生哈希碰撞的时候我们会将后添加的元素与之前就已经存在的元素形成一个链表当再次发生哈希碰撞时就继续在链表尾部添加即可。如下图所示我们也可以采取这种方式将数据库中的数据以哈希的方式存储到哈希表中可以看到h(k2)与h(k5) 就产生了哈希碰撞如果我们两个数据都想要存储就可以让 h(k5) 追加在 h(k2) 的后面形成链表当我们想要获取 h(k5) 元素的时候遍历链表即可。1.3 HashMap 的时间复杂度HashMap 是一个数组它是有下标的我们在查询/删除/修改元素的时候都可以直接通过哈希函数计算出来的哈希值精确到某个元素的位置这里不考虑哈希碰撞形成的链表因此 HashMap 的查询/删除/修改 元素的时间复杂度都是O(1)也就是常量级别的可以说是非常非常快。二. AVL树2.1 简单了解AVL树AVL树其实也叫平衡二叉树或叫平衡二叉搜索树它通常满足一个特点左子节点的值都比父节点小右子节点的值都比父节点大如下图所示在这种情况下我们去寻找数据911先查找根节点34比91小所以91在34的右半部分2查询到89还比91小所以91在89的右半部分3继续向下查找就找到了元素91只需要查找三次即可得出结果4如果查到最后没有找到说明想要查找的元素在AVL树中不存在2.2 AVL树的时间复杂度从上面举得例子不难看出在AVL树中查找数据时每查找一次砍掉一半的数据再查找一次再砍掉一半的数据所以不难看出AVL树的时间复杂度是 O(log2n)。2.3 AVL树的缺点AVL树时间复杂度虽然低但也存在一些缺点。因为AVL树要保持高度的平衡所以需要经常性旋转而旋转是非常耗费时间和性能的。并且随着数据越来越多AVL树的深度也会越来越大。如下图所示当数据达到31个的时候AVL树的高度已经有5层了。要知道每多一层与磁盘就要多进行一次IO操作磁盘交互的速度是比较慢的非常耗费时间所以我们就在想能不能把树的高度降低一些但同时又能存足量的元素呢这就有了下面要说M叉树也可以理解为B树。三. B 树经过了刚才对AVL树的分析我们也知道了当树的枝杈越多时存储的数据也越多与磁盘交互的次数也越少我们把上方的二叉树转换成三叉树当然也可以转换成四叉树五叉树都是可以的这里我就以三叉树为例。这个时候我们还是能存储31个元素并且树的高度由原来的5层降低到了4层提高了我们数据的查找效率这就是我们数据库索引的雏形我们就可以将数据库中的数据存储在树中得到如下简易模型上图中就是索引最开始形成的B树结构图左上角也有标注这个时候我们可以看到在原始B树中磁盘块1234这几个非根节点中还存放着数据呢。根节点磁盘块P1的地址值指向磁盘块2并且里面记录的主键值都是小于26的根节点磁盘块P2是地址值指向磁盘块3里面记录的数据主键值都是在26与35之间的根节点磁盘块P3是地址值指向磁盘块4里面记录的数据主键值都是大于35的根节点磁盘块的 26和35则是两条完整的数据假若我们要查询的就是26或35就会直接返回数据不需要再往下面继续查找下方的磁盘块 234 中都是同理依次往下类推。这种数据的存储方式和查找方式性能已经非常优秀了但是还有一个缺点我们将原来的2叉树转变成M多叉树目的就是为了存储更多的数据但大家看在磁盘块 234 中P1P2P3都是指针不会占用多少空间但8和12的data存储的是真实的数据(一个指针可能只占用四个或八个字节但一条真实的数据可能占用上百字节)会占用更多的磁盘空间而且这个时候还有分成了三段如果分的段更多也会存储更多的数据这就会导致我们无法存储更多的指针数据违背了我们的初衷。于是我们就可以对这个 B 树做进一步的升级(当然也不只是因为这一个原因后面我们还会说到这里先说这一点)演化成了我们现在的 B 树结构。四. B 树如上图所示就是从B树演化形成的 B 树在 B 书中我们舍弃了B书中非叶子节点也存储真实数据做法将所有的真实数据全部存放在叶子节点中这样我们的目录页就可以存放更多的指针数据。并在每一页都会添加一个数组数组中记录着该页中的所有元素并按照从小到大的顺序排列。例如上图顶层目录页33记录了数据13032033意思就是有主键值在[1320之间的数据相关信息存储在页30中主键值大于320之后的数据相关信息存储在页33中可以根据对应的地址值去对应的页中查找数据中间目录页30中存储着 11052812920920。数据存储方式与顶层目录页一样当我们想要查找1009x这条数据时先在顶层目录页做判断判断相关信息应该存储在页30当中然后在中间页30中继续查找1009x的相关信息经过判断发现该数据存放在页9中根据对应的地址值找到页9然后在页9中就可以获取到数据1009x了不管查询哪条数据都是这样的一个过程查询速度非常稳定并且中间目录页不存储真实数据只存储地址值可以存储更多的叶子节点页数据。五. 为什么数据库不采用哈希表存储数据呢这其实是一个面试题刚才我们也分析过了哈希表的时间复杂度为O(1)常量级别是最快的那么数据库存储数据时为什么不采用哈希表的形式存储呢原因有以下几点1范围查找显得无力如果我们采用哈希表的结构存储你会发现它只能满足我们对精准值得查找当我们在数据库中加入了BETWEEN...AND...或IN这些范围查找关键字的时候哈希表就没有优势了而且哈希表还是乱序的这就导致我们在进行范围查找时时间复杂度为会从O(1)退化成O(n)而我们的树形结构时间复杂度稳定在O(log2n)这个时候我们就会发现哈希表就没有优势了2排序浪费时间因为哈希表是乱序存储当我们需要进行ORDER BY 的时候每次ORDER BY底层都要排一次序而我们的树形结构在存储是就是有序的不管什么时候取数据都省去了排序的时间。我们存储3不太支持联合索引B树中是支持联合索引的并会对联合主键依次进行排序如果我们使用哈希表存储数据当我们将字段C1与字段C2联合作为主键时哈希存储就会把C1和C2作为一个整体计算哈希值不会单个做哈希值计算。这样就乱套了因为两个不一样的字段加在一起哈希值是可能相同的会产生哈希碰撞查询时可能会查询出错误的数据无法满足我们的查询要求4索引列重复时效率低计算哈希值就是为了避免哈希碰撞如果一些字段肯定会出现碰撞例如性别年龄这些字段那么哈希碰撞的概率就会非常大它会遍历哈希碰撞产生的链表上的每一个元素依次作比较非常耗时所以哈希索引通常不会用在容易出现重复的字段上六. 为什么数据库不采取B树的结构存储数据呢通过上面我对B树结构的分析我们可以得出结论B树中数据不仅存储在叶子节点中在非叶子节点也存储着数据那么为什么数据库要采用B树存储数据而不采用B书呢它们两个才存储数据时有哪些区别这也是一道经典面试题。我总结了以下几点原因1B树中非叶子节点存储数据会导致非叶子节点可存储的叶子节点数量表少间接导致存储的数据量也随之变少2当我们对数据进行修改操作时若是修改的叶子节点无可厚非若是修改的数据在非叶子节点中就会导致非叶子节点可能会发生移动非常消耗时间和性能而如果我们使用的是B树因为我们的数据都只存储在叶子节点中我们几乎只需要更改也增加节点中的数据即可效率会更高一些3相比于B树B树的查找效率不够稳定B树几乎可能稳定在三次查找内必查找到数据而B树却显得不那么稳定。七. 为什么数据库不采用 AVL 平衡二叉树存储数据呢这个问题更简单一些我总结了两点1AVL平衡二叉树为了保持平衡需要经常做旋转这是非常耗费性能的如果我们业务中经常性地做更新或者删除操作会导致数据库底层频繁的做树的旋转对我们系统的性能很不友好2二叉树的一个节点只能悬挂两个元素在面对互联网上百万大数据的情况下如果采用AVL树就会导致树的高度很大那么随着高度的增加查找效率也会越来越低八. 自适应 Hash 索引在 InnoDB 引擎中虽然本身不支持哈希索引但是它提供了一个自适应的哈希索引这个是默认开启的当我们经常性地对数据库中的同一些数据做查询操作时它就会将这些数据存放到哈希表中以便我们以后更加快速的查找。经过自适应哈希索引优化之后之前我们需要进行一层层目录的查找但是哈希表就可以让我们一步到位省去检索的时间。
HASH索引，AVL树，B树，B+树的区别？
目录一. 什么是 Hash1.1 Hash 函数1.2 Hash 碰撞1.3 HashMap 的时间复杂度二. AVL树2.1 简单了解AVL树2.2 AVL树的时间复杂度2.3 AVL树的缺点三. B 树四. B 树五. 为什么数据库不采用哈希表存储数据呢六. 为什么数据库不采取B树的结构存储数据呢七. 为什么数据库不采用 AVL 平衡二叉树存储数据呢八. 自适应 Hash 索引本篇文章是深入理解索引B树的基本原理_程序猿ZhangSir的博客-CSDN博客这篇文章的追加部分和补充的知识点没看过也没关系不影响正常理解。一. 什么是 Hash1.1 Hash 函数Hash 本身其实是一个函数又被称为散列函数它可以大幅提高我们对数据的检索效率。因为它是散列的所以在存储数据的时候它也是无序的。Hash 算法是通过某种确定性的算法(例如MD5SHA1SHA2SHA3)将输入转变成输出相同的输入结果永远会得到相同的输出。1.2 Hash 碰撞熟悉Java中 HashMap 的同学应该知道我们在往 Map 集合中存放元素的时候它会先对要往集合中存放的元素的 key 值做一个哈希运算从而确定它要存入的位置。理论上每一个对象都会存放在不同的地方但当存放的对象越来越多时有可能后来添加的元素的 key 值计算得出的结果与之前已经存入的元素的 key 的哈希值相等这种现象就被称为哈希碰撞。当产生哈希碰撞的时候我们会将后添加的元素与之前就已经存在的元素形成一个链表当再次发生哈希碰撞时就继续在链表尾部添加即可。如下图所示我们也可以采取这种方式将数据库中的数据以哈希的方式存储到哈希表中可以看到h(k2)与h(k5) 就产生了哈希碰撞如果我们两个数据都想要存储就可以让 h(k5) 追加在 h(k2) 的后面形成链表当我们想要获取 h(k5) 元素的时候遍历链表即可。1.3 HashMap 的时间复杂度HashMap 是一个数组它是有下标的我们在查询/删除/修改元素的时候都可以直接通过哈希函数计算出来的哈希值精确到某个元素的位置这里不考虑哈希碰撞形成的链表因此 HashMap 的查询/删除/修改 元素的时间复杂度都是O(1)也就是常量级别的可以说是非常非常快。二. AVL树2.1 简单了解AVL树AVL树其实也叫平衡二叉树或叫平衡二叉搜索树它通常满足一个特点左子节点的值都比父节点小右子节点的值都比父节点大如下图所示在这种情况下我们去寻找数据911先查找根节点34比91小所以91在34的右半部分2查询到89还比91小所以91在89的右半部分3继续向下查找就找到了元素91只需要查找三次即可得出结果4如果查到最后没有找到说明想要查找的元素在AVL树中不存在2.2 AVL树的时间复杂度从上面举得例子不难看出在AVL树中查找数据时每查找一次砍掉一半的数据再查找一次再砍掉一半的数据所以不难看出AVL树的时间复杂度是 O(log2n)。2.3 AVL树的缺点AVL树时间复杂度虽然低但也存在一些缺点。因为AVL树要保持高度的平衡所以需要经常性旋转而旋转是非常耗费时间和性能的。并且随着数据越来越多AVL树的深度也会越来越大。如下图所示当数据达到31个的时候AVL树的高度已经有5层了。要知道每多一层与磁盘就要多进行一次IO操作磁盘交互的速度是比较慢的非常耗费时间所以我们就在想能不能把树的高度降低一些但同时又能存足量的元素呢这就有了下面要说M叉树也可以理解为B树。三. B 树经过了刚才对AVL树的分析我们也知道了当树的枝杈越多时存储的数据也越多与磁盘交互的次数也越少我们把上方的二叉树转换成三叉树当然也可以转换成四叉树五叉树都是可以的这里我就以三叉树为例。这个时候我们还是能存储31个元素并且树的高度由原来的5层降低到了4层提高了我们数据的查找效率这就是我们数据库索引的雏形我们就可以将数据库中的数据存储在树中得到如下简易模型上图中就是索引最开始形成的B树结构图左上角也有标注这个时候我们可以看到在原始B树中磁盘块1234这几个非根节点中还存放着数据呢。根节点磁盘块P1的地址值指向磁盘块2并且里面记录的主键值都是小于26的根节点磁盘块P2是地址值指向磁盘块3里面记录的数据主键值都是在26与35之间的根节点磁盘块P3是地址值指向磁盘块4里面记录的数据主键值都是大于35的根节点磁盘块的 26和35则是两条完整的数据假若我们要查询的就是26或35就会直接返回数据不需要再往下面继续查找下方的磁盘块 234 中都是同理依次往下类推。这种数据的存储方式和查找方式性能已经非常优秀了但是还有一个缺点我们将原来的2叉树转变成M多叉树目的就是为了存储更多的数据但大家看在磁盘块 234 中P1P2P3都是指针不会占用多少空间但8和12的data存储的是真实的数据(一个指针可能只占用四个或八个字节但一条真实的数据可能占用上百字节)会占用更多的磁盘空间而且这个时候还有分成了三段如果分的段更多也会存储更多的数据这就会导致我们无法存储更多的指针数据违背了我们的初衷。于是我们就可以对这个 B 树做进一步的升级(当然也不只是因为这一个原因后面我们还会说到这里先说这一点)演化成了我们现在的 B 树结构。四. B 树如上图所示就是从B树演化形成的 B 树在 B 书中我们舍弃了B书中非叶子节点也存储真实数据做法将所有的真实数据全部存放在叶子节点中这样我们的目录页就可以存放更多的指针数据。并在每一页都会添加一个数组数组中记录着该页中的所有元素并按照从小到大的顺序排列。例如上图顶层目录页33记录了数据13032033意思就是有主键值在[1320之间的数据相关信息存储在页30中主键值大于320之后的数据相关信息存储在页33中可以根据对应的地址值去对应的页中查找数据中间目录页30中存储着 11052812920920。数据存储方式与顶层目录页一样当我们想要查找1009x这条数据时先在顶层目录页做判断判断相关信息应该存储在页30当中然后在中间页30中继续查找1009x的相关信息经过判断发现该数据存放在页9中根据对应的地址值找到页9然后在页9中就可以获取到数据1009x了不管查询哪条数据都是这样的一个过程查询速度非常稳定并且中间目录页不存储真实数据只存储地址值可以存储更多的叶子节点页数据。五. 为什么数据库不采用哈希表存储数据呢这其实是一个面试题刚才我们也分析过了哈希表的时间复杂度为O(1)常量级别是最快的那么数据库存储数据时为什么不采用哈希表的形式存储呢原因有以下几点1范围查找显得无力如果我们采用哈希表的结构存储你会发现它只能满足我们对精准值得查找当我们在数据库中加入了BETWEEN...AND...或IN这些范围查找关键字的时候哈希表就没有优势了而且哈希表还是乱序的这就导致我们在进行范围查找时时间复杂度为会从O(1)退化成O(n)而我们的树形结构时间复杂度稳定在O(log2n)这个时候我们就会发现哈希表就没有优势了2排序浪费时间因为哈希表是乱序存储当我们需要进行ORDER BY 的时候每次ORDER BY底层都要排一次序而我们的树形结构在存储是就是有序的不管什么时候取数据都省去了排序的时间。我们存储3不太支持联合索引B树中是支持联合索引的并会对联合主键依次进行排序如果我们使用哈希表存储数据当我们将字段C1与字段C2联合作为主键时哈希存储就会把C1和C2作为一个整体计算哈希值不会单个做哈希值计算。这样就乱套了因为两个不一样的字段加在一起哈希值是可能相同的会产生哈希碰撞查询时可能会查询出错误的数据无法满足我们的查询要求4索引列重复时效率低计算哈希值就是为了避免哈希碰撞如果一些字段肯定会出现碰撞例如性别年龄这些字段那么哈希碰撞的概率就会非常大它会遍历哈希碰撞产生的链表上的每一个元素依次作比较非常耗时所以哈希索引通常不会用在容易出现重复的字段上六. 为什么数据库不采取B树的结构存储数据呢通过上面我对B树结构的分析我们可以得出结论B树中数据不仅存储在叶子节点中在非叶子节点也存储着数据那么为什么数据库要采用B树存储数据而不采用B书呢它们两个才存储数据时有哪些区别这也是一道经典面试题。我总结了以下几点原因1B树中非叶子节点存储数据会导致非叶子节点可存储的叶子节点数量表少间接导致存储的数据量也随之变少2当我们对数据进行修改操作时若是修改的叶子节点无可厚非若是修改的数据在非叶子节点中就会导致非叶子节点可能会发生移动非常消耗时间和性能而如果我们使用的是B树因为我们的数据都只存储在叶子节点中我们几乎只需要更改也增加节点中的数据即可效率会更高一些3相比于B树B树的查找效率不够稳定B树几乎可能稳定在三次查找内必查找到数据而B树却显得不那么稳定。七. 为什么数据库不采用 AVL 平衡二叉树存储数据呢这个问题更简单一些我总结了两点1AVL平衡二叉树为了保持平衡需要经常做旋转这是非常耗费性能的如果我们业务中经常性地做更新或者删除操作会导致数据库底层频繁的做树的旋转对我们系统的性能很不友好2二叉树的一个节点只能悬挂两个元素在面对互联网上百万大数据的情况下如果采用AVL树就会导致树的高度很大那么随着高度的增加查找效率也会越来越低八. 自适应 Hash 索引在 InnoDB 引擎中虽然本身不支持哈希索引但是它提供了一个自适应的哈希索引这个是默认开启的当我们经常性地对数据库中的同一些数据做查询操作时它就会将这些数据存放到哈希表中以便我们以后更加快速的查找。经过自适应哈希索引优化之后之前我们需要进行一层层目录的查找但是哈希表就可以让我们一步到位省去检索的时间。
