mysql索引的数据结构,为什么用b+树

谈到索引,大家并不陌生。索引本身是一种数据结构,存在的目的主要是为了缩短数据检索的时间,最大程度减少磁盘 IO。任何有数据的场景几乎都有索引,比如手机通讯录、文件系统(ext4\xfsfs)、数据库系统(MySQL\Oracle)。数据库系统和文件系统一般都采用 B+ 树来存储索引信息,B+ 树兼顾写和读的性能...
mysql索引的数据结构,为什么用b+树
谈到索引,大家并不陌生。索引本身是一种数据结构,存在的目的主要是为了缩短数据检索的时间,最大程度减少磁盘 IO。
任何有数据的场景几乎都有索引,比如手机通讯录、文件系统(ext4\xfs\ntfs)、数据库系统(MySQL\Oracle)。数据库系统和文件系统一般都采用 B+ 树来存储索引信息,B+ 树兼顾写和读的性能,最极端时检索复杂度为 O(logN),其中 N 指的是节点数量,logN 表示对磁盘 IO 扫描的总次数。
MySQL 支持的索引结构有四种:B+ 树,R 树,HASH,FULLTEXT。
B 树是一种多叉的 AVL 树。B-Tree 减少了 AVL 数的高度,增加了每个节点的 KEY 数量。
B 树的特性:(m 为阶数:结点的孩子个数最大值)
1. 树中每个节点最多含有 m 个孩子节点 (m>=2);
2. 除根节点和叶子结点外,其他节点的孩子数量 >=ceil(m / 2);
3. 若根节点不是叶子结点,最少有两个孩子
特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点;
4. 每个非叶子结点中包含有 n 个关键字信息:(n,P0,K1,P1,K2,P2,......,Kn,Pn) 其中:
Ki (i=1...n) 为关键字,且关键字按顺序升序排序 K(i-1)< Ki
Pi 为指向儿子节点的指针,且指针 P(i-1) 指向的儿子节点里所有关键字均小于 Ki,但都大于 K(i-1)
关键字的个数 n 必须满足:[ceil(m / 2)-1]<= n <= m-1
如果一个结点有 n 个关键字,那么该结点有 n+1 个分支。这 n+1 个关键字按照递增顺序排列
所有叶子结点都出现在同一层,是所有遍历的终点位置
2021-01-21
mysql索引的数据结构,为什么用b+树
先从数据结构的角度来答。
题主应该知道B-树和B+树最重要的一个区别就是B+树只有叶节点存放数据,其余节点用来索引,而B-树是每个索引节点都会有Data域。
这就决定了B+树更适合用来存储外部数据,也就是所谓的磁盘数据。2019-06-29
mengvlog 阅读 420 次 更新于 2025-09-09 14:24:12 我来答关注问题0
  •  文暄生活科普 一文让你对mysql索引底层实现明明白白

    索引是帮助MySQL高效获取数据的排好序的数据结构,它存储在文件中,主要的数据结构包括二叉树、HASH和B-TREE(及其变种B+TREE)。下面将详细解释MySQL索引的底层实现原理。一、索引的基本概念索引是什么:索引是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用...

  •  翡希信息咨询 学习笔记—MySQL(十七)——索引(INDEX)的数据结构B+树

    设计索引结构:为了快速定位记录,可以为数据页建立一个目录。这个目录需要满足下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求。这样,通过逐级查找目录,可以快速定位到目标记录所在的页。InnoDB中的索引方案:InnoDB使用页作为管理存储空间的基本单位。随着数据的增加,需要开辟不同...

  •  翡希信息咨询 MySQL索引结构,为何选用B+树,悟了

    索引是MySQL中用于提升数据库查找速度的一种排好序的数据结构,类似于图书馆中的检索目录,能够加快数据的查询定位。在众多数据结构中,MySQL最终选择了B+树作为索引结构,这主要归因于B+树的独特优势和特性。一、索引的基本概念索引是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中...

  •  翡希信息咨询 真的,MySQL索引入门看这个就够了

    在关系数据库中,索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构。它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录,可以根据目录中的页码快速找到所需的内容。以下是MySQL索引的详细入门指南。一、...

  • 谈到索引,大家并不陌生。索引本身是一种数据结构,存在的目的主要是为了缩短数据检索的时间,最大程度减少磁盘 IO。任何有数据的场景几乎都有索引,比如手机通讯录、文件系统(ext4\xfsfs)、数据库系统(MySQL\Oracle)。数据库系统和文件系统一般都采用 B+ 树来存储索引信息,B+ 树兼顾写和读的性能...

檬味博客在线解答立即免费咨询

mySQL相关话题

Copyright © 2023 WWW.MENGVLOG.COM - 檬味博客
返回顶部