Mysql索引之B+树数据结构分享

Mysql之索引分享 索引的本质是帮助MySQL高效获取数据的数据结构。官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。本质上，索引是数据结构。 Innodb索引的种类包括B-Tree索引。B+树的出现是为了解决每次查找数据时把磁盘IO次数控制在一个很小的数量级，最好是常数数量级。在理解B+树结构之前，先提一下计算机的局部性原理：当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。 B+树结构的定义可以参见B+树，我们先看一下B+树的结构：浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示），如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点只不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。 B+树的查找过程是，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。 B+树的性质包括：通过上面的分析，我们知道IO次数取决于b+数的高度h，假设当前数据表的数据为N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N，当数字非常大时，h的值将非常小，这意味着IO次数将非常少。B+树的高度h越小，IO次数越少，查找效率越高。 B+树索引是非常重要的数据结构，它可以帮助MySQL高效获取数据，提高查询效率，减少IO次数，提高性能。