数据结构不迷茫( 二 ) _数据结构

最先被使用的是AVL平衡二叉查找树，其首先符合二叉查找树的概念，然后左右子树的高度差不超过1 。这样就可以很好的保证查找的时间复杂度了。但是其缺点也是很明显的，需要不断的对整棵树进行调整。

文章插图

这个时候我们就引入了红黑树：左右子树的高度差不超过1倍。红黑树的高度，是2logn 。其查找，插入，删除的时间复杂度都是O(logn) 。

文章插图

堆我们再来看另外一种特殊的二叉树：堆。
我们知道堆是一种完全二叉树，往往采用数据里存储。堆在很多地方都有应用，比如

优先级队列:用在赫夫曼编码、图的最短路径、最小生成树算法
TOPK问题
求动态数据中的中位数

此外，堆在排序算法中的表现也是很好的，时间复杂度是O(logn),空间复杂度为O(1)，从这个角度来讲，是要比快排和归并排序都要优秀的，但是工程中更常见的排序算法依然是快排的，那这是为什么呢？主要从2个角度来考虑：

堆排序数据访问的方式没有快速排序友好。CPU的空间局部性原理。快排中，数据是顺序访问的，而堆中是跳着访问的。
同样的数据，堆排序的交换次数多余快排。

B树和B+树这里要从mysql讲起，使用mysql来查询数据，我们比较关注的两个点是等值查询和范围查询，如：
select * from user where id=1234;select * from user where id > 1234 and id < 2345我们前面学到的数据结构中：

散列表：等值查询时间复杂度为O(1)，但可能存在hash冲突的问题，且范围查询不支持；
二分查找树：可能失衡
平衡二叉树（AVL，红黑树）：范围查询仍然不方便，且树的高度为logn；
跳表：插入、查找、删除数据的时间复杂度都为logn,同时支持区间查询，但是logn的时间复杂度仍然过高。且B+树提出于1972年，跳表提出于1989年，所以B+树才是爸爸。

综上，我们必须要降低树的高度，所以肯定是多叉树。

B树：

文章插图

B+树

文章插图

我们来对比下B树和B+树：
B B+ 存储结构每个节点存数据叶子节点存数据，非叶子节点存储索引。所以可以存放更多的数据查找性能不稳定稳定，必须查找到叶子节点范围查询不支持支持
所以，mysql的索引选择了B+树。那么B+树是怎么演化来的呢？
如果我们对二分查找树进行改造，树中的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。

文章插图

如果我们要为上亿的数据建立索引，比如，我们给一亿个数据构建二叉查找树索引，那索引中会包含大约 1 亿个节点，每个节点假设占用 16 个字节，那就需要大约 1GB 的内存空间。给一张表建立索引，我们需要 1GB 的内存空间。如果我们要给 10 张表建立索引，那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢?
答案是把索引存放到硬盘中，但是如此一来，需要从硬盘中读取数据，速度是无法忍受的，因为树高是需要IO的次数，所以要降低树高。答案是多叉树。

文章插图

那多叉树的m到底是多少比较好呢？不管是内存中的数据，还是磁盘中的数据，操作系统都是按页(一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看)来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时后，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作。