数据库（MySQL）索引的数据结构与树

 关注

发布于: 2020 年 07 月 30 日

Author：Jessie
Date: 2020/7/30
背景﻿
上一篇文章中，对基本数据结构做了介绍，那对于在数据库这类需要快速查找的架构设计中，如何使用合适的数据结构实现？ 例如：MySQL 存储数据建立索引使用B+树实现，是为什么呢？
﻿
数据结构之——树树的结构有二叉树、平衡二叉树、红黑树、B树、B+树等。
﻿
二叉排序树二叉排序树，左边比根小，右边比根大。并且左右子树都是一个二叉排序树。但是在一个极端情况下，插入序列是有序的，则可能退化成一个链表。
﻿
﻿
红黑树（Java TreeSet） 而红黑树是一种特定的二叉平衡树，利用规则，保证了树的平衡。
根节点黑色，叶子节点都是黑色空节点。 从根到叶子阶段，不会出现两个连续的红色节点。
﻿
增删节点时，会通过染色和旋转，保持红黑树平衡，避免出现不平衡二叉树的现象。也就是降低了树的高度。
数据存储在内存中红黑树效率更高，但对于磁盘访问，B树更优。
B树它的每个节点可以拥有多个孩子节点。节点越多，可以降低树的高度。但无限多，则退化为有序数组。
对于文件系统索引喜欢用B树，而非红黑树或数组？
文件系统和数据库的索引存在硬盘里，并且如果数据量大的话，不一定能一次性加载到内存中。如果一次不能加载太多，就需要每次加载一个节点，然后一个个往下找。
﻿
B-树﻿
﻿
B+树B+树是在B树基础上做了改造，数据都存储在叶子节点，而且叶子节点间加指针形成了链表。
﻿
﻿
这样对于数据库的应用场景：Select 不一定只选一条，很多时候会选多条，比如按照 ID 排序后选 10 条。
﻿
B 树需要做局部的中序遍历，可能要跨层访问。
而 B+ 树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了。
﻿
B-树和B+树的相对于数据库主要区别﻿
B-树 N叉树并且一个结点可以存多个值 但是B-树每个结点存的是索引+数据 他其实并没有真正解决范围查频繁读磁盘数据的问题
﻿
虽然能清晰的知道范围但在查询的时候也要通过递归走一遍
﻿
而B+树非叶子节点只存储索引叶子结点才是真正的存储数据而且叶子结点之间是链式结构也就是双向链表 ，当我要查找一个小于一个数值范围的时候直接向左移动链表指针即可不用再递归到上一层再走左边 所以MySQL InnoDB存储引擎选择了B+树这种数据结构 最开始用的是B-树后边不断优化现在用的是B+树。
﻿
数据库索引使用B+树总结Hash虽然快，但适用于找单个数据，而数据库的场景找一批数据。B+ 树索引有序，并且又有链表相连，它的查询效率比 Hash 就快很多了。而且数据库中的索引一般是在磁盘上，数据量大的情况可能无法一次装入内存，B+ 树的设计可以允许数据分批加载，同时树的高度较低，提高查找效率。这样红黑树就不适用。
B+ 树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了，适用于数据库的业务场景。
﻿
参考文献https://baike.baidu.com/item/%E7%BA%A2%E9%BB%91%E6%A0%91/2413209?fr=aladdin
https://blog.csdn.net/qq_43665697/article/details/101828908
https://blog.csdn.net/liuyiling_xm610/article/details/51503915
﻿