创网中国的网站,游戏优化大师,wordpress设置登录背景图片,老年人做网站数据库索引的作用是做数据的快速检索#xff0c;而快速检索实现的本质是数据结构。像二叉树、红黑树、AVL树、B树、B树、哈希等数据结构都可以实现索引#xff0c;但其中B树效率最高。MySQL数据库索引使用的是B树。二叉树#xff1a;二叉树中#xff0c;左子树比根节点小而快速检索实现的本质是数据结构。像二叉树、红黑树、AVL树、B树、B树、哈希等数据结构都可以实现索引但其中B树效率最高。MySQL数据库索引使用的是B树。二叉树二叉树中左子树比根节点小右子树比根节点大每次寻找目标值都是二分查找的方式所以二叉树的时间复杂度为Ologn。但当大量数据发生倾斜的时候极端情况下二叉树会形成链表一样的线性结构其时间复杂度为On降低了查询效率而且每次从磁盘读取一个节点到内存就进行一次IO当二叉树深度越深IO次数就越多所以综上两点二叉树不利于做索引。红黑树红黑树是二叉树的进阶版当二叉树处于不平衡的状态时红黑树就会自动左旋右旋节点使二叉树保持基本的平衡状态也保证了查询效率不会明显地降低。但当大量数据发生倾斜时红黑树并没有从根本上解决数据倾斜的问题只是不会像二叉树一样变成线性结构那么夸张。比如数据库主键递增主键一般都有上百上千万个红黑树存在这种倾斜问题那对查询性能而言也是巨大的消耗数据库不可能忍受这种毫无意义的等待。AVL树AVL树是个绝对的平衡二叉树所以AVL树不存在二叉树、红黑树的数据倾斜问题。大量的顺序插入不会导致查询性能的降低这从根本上解决了二叉树、红黑树的数据倾斜问题。但数据库查询数据的瓶颈在于磁盘 IO AVL 树是二叉树的一种每一个树节点只存储了一个数据随着插入的数据越多树的深度也越深意味着IO次数就越多所以也影响读取的效率。这就引入了B树、B树一个树节点上尽可能多地存储数据这样一次磁盘 IO 就可以加载多个数据到内存中提高查询效率。B树B树又叫平衡多路查找树一棵m阶的B树有如下性质:1树中每个结点至多有m个孩子节点即至多有m-1个关键字2每个结点中包括“n记录结点中关键字的个数”、“p0....pn孩子节点”以及“k1...kn关键字”。3除根节点外其他节点至少有ceilm/2个孩子结点。ceil函数向上取整4若根节点不是叶子结点则根节点至少有两个孩子结点。5所有叶子结点都要在同一层上。B树要求每个节点不仅包含数据的key值还有data值。而每页的存储空间有限如果data比较大的话会导致每个节点的key存储的较少当数据量大的时候同样会导致B树很深从而增加磁盘的IO次数进而影响查询效率。B树是B树的进阶版B树与B树的区别1B树中每个根结点既有key又有data数据而B树中根节点只有key没有data数据。这样可以存储较多的key降低B树的高度从而减少IO的次数。2B树中叶子结点之间没有关联而B树中叶子结点的关键字从小到大排序叶子结点相互之间有一个引用链路将叶子结点连接起来像链表一样。3B树查找数据可能不用找到叶子结点就找到数据而B树把所有的数据都放在叶子结点上所以每次查找的次数都相同B树查询速度比B树更稳定。4遍历全部结点时B树要对每一层都进行遍历而B树只需要遍历所有的叶子结点即可这有利于数据库做全表扫描。
