在学习数据结构的时候, 往往学习的思路是直奔主题, 学习各种大神们设计出来的结构精妙的数据结构但是, 这样的学习方式使各个结构在脑中形成了一个个孤岛, 没有什么联系
如果换个角度, 从问题入手, 看看为了解决特定的问题, 我们需要什么样的数据结构来更好地解决问题, 在一步步解决问题的过程中, 看看结构之间的联系是怎么样的, 这样的学习效果会不会好一些?
现在就来试一试, 从解决查找问题为切入点, 延伸到 B 树, B + 树
问题是什么?
从计算机诞生以来, 数据就未曾离开过计算机人类与计算机交互所产生的输入操作系统运行在操作系统上的软件软件处理的业务信息, 这些都是数据, 而计算机的运行过程就是对各种数据做计算的过程这时问题就来了, 计算机要处理的数据从何而来?
如何看待存储设备
数据存储在存储设备中, 比如内存硬盘
先看看内存
内存从结构上来看, 像是一个由点组成的矩阵, 行的长度是 8, 宽度则视内存大小而定, 每个点是一个 bit, 存储着 01 值一行由 8 个点组成, 即一行是 8bit, 即 1byte
CPU 访问内存的方式是通过内存地址, 每个内存地址指向的 bit 都是位于矩阵的第一列的 bit, 并且一次对内存的访问会获取 8bit(1byte) 或 16bit(2byte) 或 32bit(byte) 等等, 即获取 8n bit(n byte),n 值由 CPU 位数决定
根据 CPU 对于内存的访问方式, 可以把上边所说的由点组成的矩阵, 抽象成由 地址 - 数据 两列组成的表, 通过一个内存地址, 就能获取到相对应的数据
再看看磁盘
磁盘中的数据存储在多张盘片上, 每张盘片以圆心为轴, 划分为多个磁道, 每个磁道上等距离的分布着多个点, 点中记录着 01 信号因此要访问磁盘中的某个 bit 数据, 需要指定在哪张盘片哪个磁道哪个位置能不能通过抽象来简化对磁盘的访问? 这样尝试一下, 把每个盘片以圆心为轴分割成多个扇面, 每个扇面 512Byte, 再把每个盘片的每个扇面按顺序编上序号, 这样访问磁盘的方式就变成了通过一个扇面编号, 就能获取到相对应的 512byte 数据, 即抽象成了由 扇面标号 - 数据 两列组成的表
无论是内存, 还是磁盘, 对数据的访问都可以抽象成一张表, 表的第一列是我们取得数据需要的凭证, 第二列是对应的数据
我们可以认为, 这就是数据结构中所说的线性结构, 属于最基本最原始的结构所以无论是访问内存还是访问磁盘, 我们都认为是对线性结构的访问
下边把内存磁盘中的数据统称为线性结构
如何从线性结构找到想要的数据
完成了上边的抽象, 我们开始考虑一个问题: 假设在线性结构中存储着数据 A, 我们想通过数据 A 的标识来找到它, 该怎么做?
1. 顺序遍历
最简单的方式, 就是对线性结构从头到尾的找, 看看哪个数据是我们要的数据
顺序遍历. png
这个方式简单可行, 很容易就达到了目的
这时出现了一个新的问题, 如果线性结构的长度越来越长, 用上边的方式会怎样?
顺序遍历 2.png
如果目标数据位于第 1000 项, 我们需要比较 1000 次标识才能找到, 也就是说有 999 次无意义的比较, 尤其是在线性结构长且目标数据位于偏后的位置时
既然这样, 那可不可以避免无意义的比较来提高查找的效率?
2. 哈希表
现在尝试着在线性结构之外构造一个新的结构 -- 哈希表, 这个结构能够根据要查找的数据, 直接定位到数据的位置, 从而提高查找效率
哈希表. png
这次, 不管数据有多少, 我们能够用 1 次计算就能找到数据 A 了, 在效率上不能更快了!
这里对哈希表做了简化, 实际上会有哈希冲突的问题, 这个问题会影响查找的效率, 影响程度取决于哈希表的宽度和哈希算法的离散程度, 这里不展开讨论
不过还是存在着问题哈希表与线性结构是一一映射的关系, 这就代表了哈希表的大小会随着线性结构的增大而增大, 这在线性结构很大的情况下是一笔不小的空间开销也就是说, 哈希表是一种用空间换时间的策略
那么, 下一个问题来了: 在不牺牲空间的前提下, 能不能得到一个较高的查找效率?
3. 二叉查找树
想要不牺牲过多的空间, 同时还要得到比顺序遍历更高的查找效率, 这就代表着我们得让线性结构本身具备某种线索能够引导我们找到目标的数据所以我们把线性结构构造成树结构:
构建二叉搜索树. png
构建后的结构不够直观, 用树形表示看下:
二叉搜索树. png
可以看到, 在构建后的二叉搜索树中查找数据 A 的过程进行了 3 次比较, 而用顺序查找的方式是 3 次比较, 效率确实提高了些, 但是看上去提高的不明显我们对顺序查找和二叉搜索树查找的效率进行量化看看
假设数据量为 n
对于顺序查找, 最好的比较次数是 1, 即第一个就是目标数据; 最坏的比较次数是 n, 即最后一个是目标数据那么平均查找次数 = (n+1)/2 O(n)
对于二叉搜索树, 最好的比较次数是 1, 即根节点是目标数据; 最坏的比较次数是 log(n+1), 即根节点是叶子节点那么平均查找次数 = (log(n+1) + 1)/2 O(logn)
其实二叉搜索树的最坏比较次数是 n, 也就是当树被构建成只有左子树或者右子树的时候, 这里就不讲树的平衡了, 把注意力都放在主要的思路上所以, 我默认构建出来的树都是平衡二叉树, 下文也是一样
时间复杂度. png
看看两种查找的时间复杂度曲线, 由此看出, 当数据量大的时候, 二叉搜索树的平均查找效率高于顺序查找, 因此此结构可以满足不牺牲空间同时还能提高查找效率的需求
我们仍然能在这个方案上发现问题假设线性结构的数量极大, 内存空间已无法容纳, 那么我们就不得不在磁盘中来存储这份数据这时问题来了, 如果要在存储在磁盘中的二叉搜索树里查找数据, 需要平均访问 logn 次磁盘 (由上文的时间复杂度得出), 比如 n=100k, 则一次查找要平均访问磁盘 17 次, 这个很要命, 要知道读取机械硬盘的时间是几十毫秒的级别, 即使是 SSD 也得是几十微秒, 这和读取内存的纳秒级别的速度差距非常大因此, 在这种情况下, 硬盘的读取速度导致了二叉搜索树的查找速度非常缓慢
既然硬盘的读取速度是效率的瓶颈, 那么能不能找到某种方式, 通过减少读取硬盘的次数来提高效率?
B 树
在二叉搜索树中查找数据, 每向下遍历一层, 则需要多访问一次磁盘那么, 可以通过减少树的深度来减少读取磁盘的次数
我们在二叉搜索树的基础上, 拓展一下每个节点, 即让每个节点从只能存储一份数据, 拓展到最多存储两份数据这样每个节点能够存储 1 份或 2 份数据, 所以每个节点长度不一定相等, 需要通过指针来指向下一个节点, 这个就是 B 树
2-3 树. png
可以看出来, 拓展之后的树的深度比原来少了 1, 所以最坏的情况下比较次数比原来少了 1 次, 达到了减少访问磁盘次数的目的
那我们猜想一下, 如果再扩展每个节点的数据, 拓展成 3 份 4 份....m 份, 那么节点会越来越宽, 树的深度会越来越小
假设我们构建了一棵每个节点存储 8 份数据深度为 3 的 B 树, 那么深度为 1 的节点有 1 个, 总共存储了 1*8=8 份数据; 深度为 2 的节点有 1*(8+1)=9 个, 总共存储了 9*8=72 份数据; 深度为 3 的节点有 9*(8+1)=81 个, 总共存储了 81*8=680 份数据综上, 总共可存储 8+72+680=760 份数据也就是说我们对这 760 份数据做查找最多访问磁盘 3 次, 和上边说的存储了 7 份数据的搜索二叉树持平
为了达到效率最优, B 树的节点大小往往被设置成与磁盘扇区大小一致, 一般为 512 因为一般读取磁盘的单位是扇区, 这样的设置充分利用了每次对磁盘的读取, 从而减少读取次数
B 树解决了磁盘读取过多导致查找效率低的问题, 但它存在着查找之外的其他问题: 如果我们想按顺序遍历一遍所有数据, 需要怎么做? 以上面的图为例, 遍历 A->B->C->D->E->F, 这个过程中访问了两次 B 和 F 所在节点也就是说非叶子节点需要访问多次, 这样并不理想
那么, 有什么办法能在满足 B 树特性的前提下还可以高效的顺序遍历所有数据?
B + 树
把 B 树节点中的数据都放到叶子节点中, 而非叶子节点中只保留标识和指针, 看看结构是什么样的:
B + 树. png
它依然保留着 B 树的特性, 同时还有些不同 B + 树只有遍历到了叶子节点才能获取到数据, 非叶子节点中只有标识信息, 这导致查找的效率变低了, 但这换来的是所有数据都集中在了叶子节点中, 从而能够按顺序串联在一起, 实现高效的遍历
总结
本文从对存储设备中的数据做查找的问题开始讨论, 一步步找到解决方案, 同时发现新的问题, 如此往复直到延伸到 B + 树这里没有讨论具体的细节, 比如如何解决哈希冲突如何构建平衡二叉树等等, 我希望把注意力放在在发现问题和解决问题的过程中, 在这个过程中逐渐衍生出新的结构, 并用这些结构来解决特定的问题, 从而对这些结构能有个新的认识
这里只涉及了小部分的数据结构和查找这一个问题域, 其他的结构和问题还有很多, 我相信也可以通过这种形式来思考一下, 也许也会有同样新的认识
如果本次的讨论有那些不严谨的地方, 希望发现的人能帮我纠正一下, 算是对我的帮助吧
欢迎交流~
来源: http://www.jianshu.com/p/65e48347d953