索引第一篇：B+树索引、哈希索引、全文索引

2023-06-14 04:01| 来源: 网络整理| 查看: 265

文章目录一、前言二、从B树到B+树 2.1 B树 2.1.1 B树性质 2.1.2 B树查找 2.1.3 B树插入 2.1.4 B树删除 2.2 B+树（性质、插入、删除、查找、范围查找） 2.3 小结三、B+树索引 3.1 索引有哪些数据结构 3.2 B+树数据结构的优势（哈希表、二叉树、平衡二叉树、B树、B+树）？ 3.2.1 Hash索引 3.2.2 有序数组 3.2.3 二叉树做索引 3.2.4 平衡二叉树做索引 3.2.5 用B树做索引 3.2.6 用B+树做索引 3.3 B+树中一个节点到底多大合适？ 3.4 B+树作为索引，特征决定优势四、哈希索引、全文索引 4.1 哈希索引 4.2 全文索引五、尾声一、前言

人们谈论索引的时候,如果没有特别指明类型,那多半说的是B+Tree索引（MySQL默认存储引擎是InnoDB存储引擎，InnoDB存储引擎使用的是B+树索引）,它使用Tree数据结构来存储数据。

尽管大多数MySQL引擎都支持B+树索引，即使是使用B+树索引，不同存储引擎的实现方式也有所不同：（1）MyISAM 使用前缀压缩技术使得索引更小,但 InnoDB则按照原数据格式进行存储；（2）MyISAM 索引通过数据的物理位置引用被索引的行,而 InnoDB则根据主键引用被索引的行。

注意：只有B树和B+树，没有B-树。

二、从B树到B+树 2.1 B树

B树(B tree)是一种平衡的多路查找树,主要面向动态查找,通常用在文件系统中。

2.1.1 B树性质

一棵m阶的B树两种情况，要么为空树,要么为满足下列特性的m叉树：

(1)叶子节点：所有的叶子结点都出现在同一层,并且不带信息。叶子结点的双亲称为终端结点;

(2)每个节点：每个结点至多有m棵子树;（金手指：m叉树）

(3)根节点：若根结点不是终端结点,则至少有两棵子树;

(4)非根节点：除根结点之外的所有非终端结点至少有⌈m/2⌉棵子树;

(5)非终端节点(非叶子节点)：所有的非终端结点都包含以下数据: (n,A0,K1,A1,K2,…,Kn,An)

其中,n(⌈m/2⌉-1≤n≤m-1)为关键码的个数,Ki(1≤i≤n)为关键码,且Ki

【本文地址】

公司简介

联系我们