msyql 为什么要使用B+树 | LaiYong Wang

msyql 为什么要使用B+树

Laiyong Wang Lv6

2022-11-17 00:10:10 2025-01-07 15:52:37

为什么呢

为什么不使用二叉树、平衡树、红黑树、或者B树

首先确认一点

二叉树、平衡树、红黑树、尤其是红黑树
B树
他们的搜索速度的确够快
但是运用至计算机，其速度需要受到I/O制约
所以二叉树、平衡树、红黑树的深度太深，io次数太多，浪费性能
B树是因为数据和节点保存在一起，相同数量的数据，其深度会比较大

为什么会比较大？
先说明一种情况
正常是cpu和内存进行交互，内存和磁盘进行交互
磁盘读取是按页的，正常是4k或者8k
节点和数据同时保存，每页保存的数量肯定会变少，为了保存更大数据量的数据，树的深度肯定会加深

使用B+树

B+ 树除了页子节点，所有非页子节点都不保存数据，所以每页数据可以保存非常多的数量，间接导致同深度的树能保存更多的数据

引申出的问题

分表

水平分表
很容易理解，降低深度和减少数据量，就是为了降低io次数
垂直分表
原理是将大字段的io效率低，那就拆分出去，本表做查询然后做关联查询
为啥能提高速度

每次查询，内存很小，可以缓存，若是使用的都是短查询的话，缓存全命中，速度极大替快
数据量小了，查询肯定快
内存和存储是以页进行查找和定位的，单叶内数据越多，肯定io效率越好，速度越快

$li-margin-bottom = 0.8rem $post-tool-button-width = 2.5rem .post-tools-container { padding-top var(--component-gap) .post-tools-list { li { margin-bottom $li-margin-bottom &:last-child { margin-bottom 0 } } li.tools-item { position relative box-sizing border-box width $post-tool-button-width height $post-tool-button-width color var(--text-color-3) font-size 1.2rem background var(--background-color-1) border-radius 50% box-shadow 2px 2px 5px var(--shadow-color) cursor pointer &:hover { box-shadow 2px 2px 8px var(--shadow-hover-color) } i { color var(--text-color-3) } &:hover { color var(--background-color-1) background var(--primary-color) i { color var(--background-color-1) !important } } &.toggle-show-toc { display none } &.go-to-comments { .post-comments-count { position absolute top 0 right -1rem display none align-items center justify-content center box-sizing border-box min-width 1.1rem height 1.1rem padding 0 0.2rem color var(--badge-color) font-size 12px background var(--badge-background-color) border-radius 0.4rem +keep-tablet() { display none !important } } } } li.status-item { width $post-tool-button-width height $post-tool-button-width color var(--text-color-3) font-size 1.6rem cursor pointer &.post-lock { cursor default .fa-lock-open { display none color var(--keep-success-color) } &.decrypt { cursor pointer .fa-lock-open { display block } .fa-lock { display none } } } } } }