网址大全网站,网站描述标签优化,云商城的网站建设,网站管理系统推荐1. 磁盘基础知识 分页#xff1a;
现代操作系统都使用虚拟内存来印射到物理内存#xff0c;内存大小有限且价格昂贵#xff0c;所以数据的持久化是在磁盘上。虚拟内存、物理内存、磁盘都使用页作为内存读取的最小单位。一般一页为4KB#xff08;8个扇区#xff0c;每个扇…1. 磁盘基础知识 分页
现代操作系统都使用虚拟内存来印射到物理内存内存大小有限且价格昂贵所以数据的持久化是在磁盘上。虚拟内存、物理内存、磁盘都使用页作为内存读取的最小单位。一般一页为4KB8个扇区每个扇区512B8*512B4KB。 局部性原理 当一个数据被用到时其附近的数据也通常会马上被使用。 程序运行期间所需要的数据通常比较集中。 磁盘预读原理
磁盘读取依靠的是机械运动分为寻道时间、旋转延迟、传输时间三个部分这三个部分耗时相加就是一次磁盘IO的时间大概 9ms 左右。这个成本是访问内存的十万倍左右
磁盘读取的速度远小于内存所以尽量减少 I/O 次数是提高效率的关键。
根据局部性原理且由于磁盘顺序读取的效率很高不需要寻道时间只需很少的旋转时间所以即使只需要读取一个字节磁盘也会读取一页的数据。即磁盘预读时通常会读取页的整倍数。
2. 树基础知识回顾
排序二叉树左 跟 右 B 树有序数组 多叉平衡树节点存储关键字、数据、指针 B 树有序数组链表 多叉平衡树非叶子节点存储指针、关键字不存储数据 红黑树红黑树是一种不大严格的平衡树平衡树要求太高 平衡树是为了防止二叉查找树退化为链表而红黑树在维持平衡以确保 O(log2(n)) 的同时不需要频繁着调整树的结构 二叉树的存储结构 顺序存储适用于完全二叉树 index 之间的对应关系 注意二叉树的顺序存储只适合存储完全二叉树否则 index 无法和节点对应起来会有点恶心 链式存储 这里要好好理解一下不然会影响后面的理解。 相关视频推荐
4种红黑树的使用场景从linux内核到应用开发epoll、sk_buff、虚拟内存管理、nginx流量监控
90分钟搞定红黑树应用
后端开发必学4种层式结构B/B-树、时间轮、跳表、LSM-Tree
免费学习地址c/c linux服务器开发/后台架构师
需要C/C Linux服务器架构师学习资料加qun812855908获取资料包括C/CLinuxgolang技术NginxZeroMQMySQLRedisfastdfsMongoDBZK流媒体CDNP2PK8SDockerTCP/IP协程DPDKffmpeg等免费分享 3. 为什么不能使用二叉树来存储数据库索引
先说结论 平衡二叉树进行插入/删除时大概率需要通过左旋/右旋来维持平衡 旋转需要加载整个树频繁旋转效率低 二叉树的 I/O 次数近似为 O(log2(n)) 范围查询时二叉树的时间复杂度会退化成 O(n) 二叉树退化成链表时时间复杂度也近似退化成了 O(n) 二叉树无法使用磁盘预读功能
其实单论范围查询在关系型数据库中就基本没有使用二叉树的可能了。但是为了加深对知识的了解来看看其他的原因。
先剔除掉范围查询的情况原因 1、2、6 可以通过红黑树来解决那么其实就剩下 2 个原因 I/O 次数对比 磁盘预读功能的利用
4. 二叉树的 I/O 次数分析
先说 I/O 次数
其实相比于二叉树B 树、B树 CPU 的运算次数并没有变化甚至增多。但是 CPU 运算次数相比于 I/O 的消耗而言可以忽略不计所以 I/O 次数是评价一个数据库索引的效率高低的关键指标。
对于红黑树而言其 I/O 次数近似为 log2(n)为什么是近似呢
首先索引是存储在磁盘上的磁盘上的数据大部分情况下是连续的但是随着增删改查的发生有可能产生很多碎片也就是说 索引在磁盘上的存储也不一定是连续的
这里严谨起见我们来分两种情况 索引节点即树的节点在磁盘上存储是连续
假设一个页能存储 5 个节点假设二叉树如下 注意序号只代表在磁盘中存储的顺序不代表对应节点的关键字的值 二叉树可能是链式存储也可能是顺序存储。但是这里假设节点在磁盘上的存储是连续的所以这里可以近似理解成顺序存储。即使是链式存储无非就是 pNext 指针指向下一个连续的内存地址而已。
现在假设搜索的结果是最左边的叶子节点 16因为磁盘预读的特性加上一个页能存储 5 个节点第一次 I/O 添加图片注释不超过 140 字可选
如上第一次 I/O 就读取了 5 个节点不仅把根节点读取进内存了还把节点 2 和 4 都读取进去了看上去还节约了两次 I/O 好厉害的样子……
此时会根据二分法查找对比 1 号节点然后去找节点 2紧接着找节点 4因为这两个节点都在内存中了所以不需要进行 I/O 这里再说一次序号不代表节点的关键字而是单纯的表示节点在磁盘中的排列顺序 紧接着会需要 8 号节点而 8 不再内存中所以进行第二次 I/O 同样是读取一页即 5 个节点 这次虽然也是读取了 5 个节点但是实际上只有 8 号节点有实际作用其他节点并没什么卵用这是二叉树无法使用预读功能的本质但是现在还没体现出劣势现在对比之后需要 16 号节点继续第三次读取 此时找到了 16并将结果返回。
这是高度为 4 的情况且只有 31 个数据。但是实际使用中怎么可能就 31 个数据假设要找的是 32 号节点因为 16 号节点之后的 17-20 虽然被加载进内存了但是完全没用。那么就需要再进行一次 I/O 来加载 32 号节点所在的页同时也会将 33-36 加载进内存但是这些节点并无卵用。
如果要找的是 1000 10000
所以随着层级的深入会出现 一个页中只有一个节点有用二分法查找要的是子节点而不是兄弟节点 I/O 次数近似等于log2(n)
即 第一次 I/O 可能的优势在层级加深之后就没有了 就算是红黑树也只能将时间复杂度维持在 log2(n)
上述讨论的是索引树在磁盘上的存储是连续的如果不是连续的那么按页读取到的脏数据会更多上述的情况中前几次 I/O 读取到有用的数据的概率会变低所以 I/O 的次数只会增多而不会减少,即仍然是近似于 log2(n)。
5. B/B树
B 树即多路平衡查找树
B 树的巧妙之处在于 将一个节点的大小设置为一页的大小 一个节点可以存放多个关键字多叉树 自平衡
这 3 点结合起来就可以做到 一个节点大小为一页被加载进内存时这些关键字在进行对比找出需要 leftChild 还是 rightChild 时都是有用的如最右侧时需要对比所有节点 一个节点可以存储多个关键字有效降低了树的高度
B 树的巧妙之处在于 非叶子节点不存储数据进一步增大了一页中存储关键字的数量 叶子节点中存储数据且存在指向下一页的链表指针可以使用顺序查询支持范围查询
6. B/B树的索引数量
B 树的节点中存储指针、关键字(主键)、数据 B 树的非叶子节点指针、关键字 B树的叶子节点指针(链表)、关键字、数据 注意这里不是绝对的比如有的 B 树中叶子节点存储的不是数据而是指向数据的指针。查询到指针之后再去对应地址取出数据但是这样应该会增加一次 I/O 吧应该也是在数据量和 I/O 次数之间做了取舍具体先不讨论。 以 Sqlite3.12 之后为例page_size 16k假设指针为 8 byte假设关键字类型占 8 byte假设数据占 1 KB
B 树的一个节点 一页能存储的数据量为16kb / (1KB8byte8byte) ≈ 16
高度为 3 的 B 树能存储 16 x16 x16 4096 条数据
相比于二叉树的 1 个而言确实有效降低了树的层级。而且上述是假设数据为 1KB如果数据没那么大高度为 3 的 B 树能存储更多的数据但是如果用在大型数据库索引上还是不够。
B 树 如上图B树的核心在于非叶子节点不存储数据。
这样做可以减少非叶子结点占用的空间增大一页所能存储的数据量最大程度减少树的层级。
仍然是以上假设假如树的高度为 3 那么就有两层存储关键字指针一层叶子节点来存储实际数据。
一页能存储的关键字为16 * 1024 / (8 8) 1024 一页能存储的数据量为16KB / (1KB 8byte 8byte) 16 这里计算不完全准确实际情况应该是1页数据中只有一个链表指针指向下一页 能存储的关键字为1024 * 1024 1048576
因为端节点又有 1024 个指针这些指针可以指向一个页页中存储数据也就是叶子节点一页能存储 16 个叶子节点所以总共能索引的数据量为 1048576 * 16 ≈ 1600万如果高度为 4 则再乘以 1024 约为 17亿…..
上述推理中理解终端节点的指针指向一个页页中存储着关键字 数据 链表指针是关键。page 标记如下有助理解 虽然叶子节点很多一个 page 对应一个叶子节点甚至是多个 page 才能存下一个叶子节点但是这些是存在磁盘上的找到对应的 page 之后才去加载对应的 page。索引超大数据量的同时不会对 I/O 次数产生影响这就是这个设计的牛逼之处。 但是这样也是有缺点的
无论查询结果如何都必须走到叶子节点才结束也就是 I/O 次数固定为 O(h) 或者说是 log(n)底数为节点子分支个数这个 h 一般为 2-3排除掉根节点常驻内存高度为 3 的 B 树进行两次 I/O 就可以索引千万级别的数据,高度为 4 的 B 树进行 3 次 I/O 就能索引十亿级别的数据量这个效果还是很好的。
所以这个缺点也可以说成是优点稳定稳如一条老狗
7. 实际应用 红黑树优点
红黑树常用于存储内存中的有序数据增删很快内存存储不涉及 I/O 操作。 B/B树的优点
更适合磁盘存储减少了树的层级进而减少 I/O 次数 B 树和 B 树对比
都是 B 树但是 B树更适合范围查询比如 Mysql且查询次数很稳定为 logn。而 B 树更适合键值对型的聚合数据库比如 MongoDB查询次数最优为 O(1) 红黑树更适合内存存储B 树更适合键值对存储B 树适合范围查询
