数据库索引原理以及BTree,B+Tree

朴灿烈づ我的快乐病毒、 2024-04-18 08:39 63阅读 0赞

1.索引的种类

*  众所周知，索引类似于字典的目录，可以提高查询的效率。
 *  索引从物理上可以分为：聚集索引也叫聚簇索引。，非聚集索引也叫非聚簇索引。
 *  从逻辑上可以分为：单列索引（普通索引，唯一索引，主键索引），联合索引，全文索引
 *  如果不创建索引，系统会自动创建一个隐含列作为表的聚集索引。（用户不可见）而MySQL里主键就是聚集索引
 *  除了聚集索引以外的索引都是非聚集索引
 *  如上面的普通索引，唯一索引，全文索引，联合索引就是非聚集索引，主键索引就是聚集索引

2.什么是聚集索引，非聚集索引

*  聚集索引：索引数据的物理顺序与数据库中的真实列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。而且由于物理排列方式与聚集索引的顺序相同，所以也就只能建立一个聚集索引了。
 *  举例：聚集索引就像是字典的拼音目录，而每个字存放的页码就是我们的数据物理地址，拼音目录对应的A-Z的字顺序，和新华字典实际存储的字的顺序A-Z也是一样的
 *  非聚集索引：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。
 *  举例：非聚集索引就像新华字典的偏旁字典，他结构顺序与实际存放顺序不一定一致。

3.区别

*  使用聚集索引查询：由于聚集索引的叶子节点就是对应的数据的物理位置（主键的行号），因此在查询方面，聚集索引的速度往往会更占优势
 *  非聚集索引叶节点仍然是索引节点，只是有一个指针指向对应的数据块，此如果使用非聚集索引查询，而查询列中包含了其他该索引没有覆盖的列，那么他还要进行第二次的查询，查询节点上对应的数据行的数据。
 *  两种方式索引的根本区别：1.表记录的排列顺序和与索引的排列顺序是否一致。2.聚集索引一个表只有一个，非聚集索引一个表可以存在多个。3.聚集索引存储记录是物理上连续存在，非聚集索引是逻辑上的连续。

4.查询问题

*  主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚集索引（clustered index）。
 *  非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。
 *  如果语句是 select \* from T where ID=500，即 主键查询方式，则只需要搜索 ID 这棵 B+树 ；
 *  如果语句是 select \* from T where k=5，即 普通索引查询方式，则需要先搜索 k 索引树，得到 ID的值为 500，再到 ID 索引树搜索一次。这个过程称为回表（也叫做二次查询）
 *  不管以任何方式查询表， 最终都会利用主键通过聚集索引来定位到数据， 聚集索引（主键）是通往真实数据所在的唯一路径，（有一种例外可以不使用聚集索引就能查询出所需要的数据那就是「覆盖索引」查询，覆盖索引查询能省去第二步再根据主键通过聚集索引来定位数据）
 *  [mysql索引篇][mysql]
 *  当面试被问到如果一个表没有设置主键通过非聚集索引查找时会怎么样？答案是：如果用户自己没为表创建主键，就如上面所讲系统会自动创建一个隐含列作为表的主键并且对用户不可见（直针对数据库存储引擎为innodb的）

**问题点**：

1.  创建索引问题（[索引生成问题][Link 1]）

*  创建两个单列索引（A和B）和创建一个包含两列的联合索引（AB）有什么区别？
 *  单列索引：会生成两课索引树，一个是A索引树，一个是B索引树（猜想：当使用条件=A and 条件=B时，从A和B两课树种查到满足的数据主键id然后再用id值去聚集索引树中查找真正的一条数据，然后再根据条件进行筛选出正确的数据加入结果集中并返回。）
 *  联合索引：也会生成两棵索引树，一个是A索引树，一个数AB索引树，所以当对联合索引进行条件B查询时是不会走索引的因为没有，这也就是联合索引的最左前缀原则。最左前缀原则只针对联合索引来讲。（ABC列建立联合索引，会生成A，AB,ABC索引树，不会生成AC,BC，所以这也是使用联合索引时中间不能断层，不然还是会引起全表扫描的，**最佳左前缀法则（带头索引不能死，中间索引不能断**）
 *  创建的索引是存储在磁盘上的，当查询是把磁盘索引数据读入到内存 
 *  [索引使用案列][Link 2]

2.  mysql中是如何对字符串建立索引的

*    对字符串的字段建立索引有三种方式，1、普通索引，2、前缀索引、3、倒排索引
 *  1、什么是普通索引：例如对name 建立完整索引，那么就会把name字段中所有的字符串都建立索引，查询时比较精确，但是占用空间也多
 *  2、前缀索引：就是只对前几个字符加索引，这样可能查询比较次数要多一些，但是占用空间少：[参考][Link 3]
 *      只对字符串的前几个字符进行索引。通过字符串的前几个字符我们已经能大概排序字符串了，
        剩下不能排序的可以通过遍历进行查找啊，这样只在B+树中存储字符串的前几个字符的编码，
        既节约空间，又减少了字符串的比较时间，还大概能解决排序的问题，
        何乐而不为，比方说我们在建表语句中只对name列的前10个字符进行索引可以这么写：
        CREATE TABLE person_info(
            name VARCHAR(100) NOT NULL,
            birthday DATE NOT NULL,
            phone_number CHAR(11) NOT NULL,
            country varchar(100) NOT NULL,
            KEY idx_name_age_birthday (name(10), birthday, phone_number)
        );  
        name(10)就表示在建立的B+树索引中只保留记录的前10个字符的编码，
    
     
 *  3、倒排索引：和前缀索引类似，只是把后几个字符串简历索引，针对身份证号这样的大部分前面相同后几位不同的字符建立倒排索引合适
 *      比如某个字段存储的是身份证号，我们知道索引列的差异性越大，
        使用索引的收益越高，如果我们使用前缀索引的话，
        因为身份证号前几位标识的地区码，重复较多，
        如果建立前缀索引的话，要建立12位才能满足一定的区分度。
        但是显然是浪费空间的。那么我们可以建立数据的倒序索引，
        新建数据时倒序插入，查询时使用 select * from t where id_card = reverse(idCard)进行查询
    
     
 *  [参考][Link 4] ，[对字符串创建的索引类型][Link 4]

5.插入数据问题

*  聚集索引在插入新值的时候需要做必要的维护。以上面为例，如果插入新的行 ID 值为 700，则只只需要在 500 的记录后面插入一个新记录。如果新插入的 ID值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。然后再把id为400的数据插入进去（所以添加数据会引起数据顺序的重组）
 *  非聚集索引在插入新值，因为索引的顺序不需要跟实际数据的顺序保持一致，所以不需要移动数据，也就不会引起数据顺序的重组，效率较高
 *  **在InnoDB中，我们应该尽量使用和应用无关的主键，例如自增主键，这样可以保证数据行是按照顺序写入的**。而不是使用GUID、UUID生成随机的主键
 *  在使用自增主键时每次插入数据都只会在前一天记录后面插入不会引起数据数据重组
 *  而如果使用uuid等无序的值作为主键新的记录可能被插入到之前记录的中间，导致需要强制移动之前的记录：被写满且已经刷到磁盘上的页可能会被重新读取用于再次插入，此时还需要进行页分裂：
    
     *  ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 1][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 2][]

6.B+Tree和 B-Tree（简称B树）

注：B-Tree就是我们常说的B树，一定不要读成B减树，否则就很丢人了

*  B-Tree特点：

1.所有键值分布在整个树中

2.搜索有可能在非叶子节点结束（因为b数的数据存储方式是键和值在整棵树中都有，并不一定数据只在叶子节点存储）

3.每个节点中有key，也有data，而每一个页的存储空间是有限的，如果**data数据较大时**将会导致每个节点（即一个页）能存储的 key 的数量很小。

4.当存储的**数据量很大时**同样会导致 B-Tree 的深度较大，增大查询时的磁盘 I/O 次数，进而影响查询效率

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 3][]

*  B+Tree特点：

1.B+Tree 是在 B-Tree 基础上的一种优化，InnoDB 存储引擎就是用 B+Tree 实现其索引结构

2.非叶子节点存储key，叶子节点存储key和数据，所有数据都存储在叶子节点，非叶子节点不存储真正的data

3.因为b+tree非叶子结点不会存储数据，所以每页可以包含更多的节点，这样做有两个原因,一个是降低树的高度。另外一个是将数据范围变为多个区间，区间越多，数据检索越快

4.注：MySQL 的 InnoDB 存储引擎在设计时是将根节点常驻内存的，因此力求达到树的深度不超过 3，也就是说 I/O 不需要超过 3 次。这样效率就会很高

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 4][]

7.B-树和B+树的区别

*  B+树内节点不存储数据，所有数据存储在叶子节点导致查询时间复杂度固定为 log n
 *  B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)
 *  B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等

8.MongoDB 为什么使用B-树

*  B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。尽可能少的磁盘 IO 是提高性能的有效手段。MongoDB 是聚合型数据库，而 B-树恰好 key 和 data 域聚合在一起。
 *  至于MongoDB为什么使用B-树而不是B+树，可以从它的设计角度来考虑，它并不是传统的关系性数据库，而是以Json格式作为存储的nosql，目的就是高性能，高可用，易扩展。首先它摆脱了关系模型，上面所述的优点2需求就没那么强烈了，其次Mysql由于使用B+树，数据都在叶节点上，每次查询都需要访问到叶节点，而MongoDB使用B-树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql。

9.Mysql中InnoDB和MyISAM对比

*  在MySQL 5.5之前的版本中，默认的搜索引擎是MyISAM，从MySQL 5.5之后的版本中，默认的搜索引擎变更为InnoDB。
 *  首先mysql中InnoDB和MyISAM引擎都是使用B+Tree作为索引结构。但是两者又有不同
 *  相同点：InnoDB和MyISAM中的主键索引（也就是一级索引）存储方式是相同的，主索引中存储的是key是主键值，value是该数据的行号（或数据的实际物理地址），然后通过此行号进行回表查询需要的数据。
 *  不同点：二级索引（非主键索引）存储是不同的
    
     *  在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复
     *  InnoDB中，主索引和辅助索引有很大的区别，主索引中存储的是key是主键值，value是该数据的行号（或数据的实际物理地址），而辅助素银（二级索引）中存储的key是索引字段的值，value是主键的值，这样就需要两次查询，根据主键值再去查询主索引中的数据行号。
     *  这也正是为什么在查询（select）上MyISAM的效率要高与InnoDB了
     *  但是同样的InnoDB支持了很多MyISAM不支持的东西，所以现在mysql的默认引擎是innodb了
     *  ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 5][]
 *

9.1InnoDB 中的 B+Tree

*  InnoDB 是通过 B+Tree 结构对 ID 建索引，然后在叶子节点中存储记录。
 *  若建索引的字段不是主键 ID（也就是不是聚集索引），则对该字段建索引，然后在叶子节点中存储的数据是该记录的主键值，然后通过主键索引进行二次查找找到对应的记录。（这也就是普通索引非聚集索引的查询）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 6][]

9.2 Myisam 中的 B+Tree

*  Myisam 引擎也是采用的 B+Tree 结构来作为索引结构。由于 Myisam 中的索引和数据分别存放在不同的文件，所以在索引树中的叶子节点中存的数据是该索引对应的数据记录的地址，由于数据与索引不在一起，所以 Myisam 是非聚簇索引。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 7][]

**10、为什么Mysql选择B+TREE索引? B+TREE索引有什么好处?**

*  索引的性能优势： 一般使用磁盘I/O次数评价索引优劣。
 *  索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数，提升索引效率。
 *  B+Tree 单个节点能放多个子节点，相同IO次数，检索出更多信息。
 *  B+TREE 只在叶子节点存储数据 & 所有叶子结点包含一个链指针 & 其他内层非叶子节点只存储索引数据。只利用索引快速定位数据索引范围，先定位索引再通过索引高效快速定位数据。

11、索引文件的存储

*  聚簇索引： 索引 和 数据文件为同一个文件。非聚簇索引： 索引 和 数据文件分开的索引。
 *  **MyISAM索引原理：MyISAM 采用的是非聚簇索引，索引文件myi和数据文件myd是分开存储的，索引文件仅保存数据记录的指针地址，叶子节点保存这指向数据的物理地址，**MyISAM索引按照B+Tree搜索，如果指定的Key存在，则取出其data域的值，然后以data域值-数据指针地址去读取相应数据记录，辅助索引和主索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。MyISAM索引树如下：
 *  ![format_png][]
 *  **InnoDB索引原理：采用的是聚簇索引- InnoDB中数据文件和索引文件为同一个idb文件，表数据文件本身就是主索引，因为innodb中索引文件和数据文件是同一个，所以b+tree中的叶子节点中存储的就不是数据的内存地址了，而是真正的数据**
 *  注：由于InnoDB采用聚簇索引结构存储，索引InnoDB的数据文件需要按照主键聚集，因此InnoDB要求表必须有主键(MyISAM可以没有)。
 *  聚簇索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得数据记录主键，然后用主键到主索引中检索获得数据记录
 *  ![format_png 1][]

附总结：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 8][]

借鉴资料：[mysql索引底层原理分析][mysql 1]

[mysql]: https://www.jianshu.com/p/bdc9e57ccf8b
[Link 1]: https://blog.csdn.net/cherry_xiu/article/details/79456872
[Link 2]: https://blog.csdn.net/wuseyukui/article/details/72312574
[Link 3]: https://blog.csdn.net/u011383596/article/details/80359740
[Link 4]: https://www.cnblogs.com/25-lH/p/10978727.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190920110152894.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190920110219501.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/d2453422fd364525a05b20ddc8dd01f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b2da043b785f41d99c3d395d2fe582ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/e07ed28d30fd4548a27de3ed1eeba8ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/716664a5a65b4a809c2cded4550a4649.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/44340bac75e245a38c80a505582c7b69.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/09b4e75a532b40338869bd69c59b0606.png
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zNTc1MDQ4LTQxY2E4ZDA3NjRiNGUzNGQucG5n?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zNTc1MDQ4LWU4MWFjNjhjNDAyMDk0NWUucG5n?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NTQ1NzEz_size_16_color_FFFFFF_t_70 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/762a302cd6234a9ca6962cfc379ef6fe.png
[mysql 1]: https://blog.csdn.net/alex_xfboy/article/details/82818753#%E5%89%8D%E8%A8%80%EF%BC%9Ainnodb%E5%92%8Cmyisam%E7%9A%84%E5%8C%BA%E5%88%AB