B树结构表是什么意思

白鳝的洞穴 2021-07-31

961

昨天看达梦的基础概念的时候，发现达梦的存储引擎有多种数据组织方式：B树数据、堆表数据、列存数据、位图索引。其中B树数据是普通的达梦表的默认组织方式。看到这里，Oracle dba就会有些奇怪了，按照Oracle的组织方式，默认的表应该是堆表才对啊，为啥是B树数据组织方式呢？不仅仅是达梦数据库，其实Mysql的Innodb引擎，其表的默认组织方式也是类似B树的结构。B树结构的数据组织方式实际上一张表创建的时候会创建两个段，其中一个段是索引段，一个段是叶节点段。索引段在达梦数据库中被称为内节点段，存储表数据的段称为叶子段。

目前还看不到达梦具体的技术实现的细节，不过对于采用类似结构的Mysql Innodb引擎，我们可以找到很多关于存储引擎逻辑结构的资料，我们来看下面的一张图。

表空间是一个逻辑结构，可以被认为是innodb的顶层逻辑结构，所有的数据都必须属于某个表空间。默认的innodb引擎有一个ibdata1表空间，默认的数据都存储在这个表空格键中。如果设置了innodb_file_per_table参数，每张表都会创建独立的文件。不过只有表的数据、索引等会存储在每张表自己的文件中，UNDO数据、事务控制信息、INSERT BUFFER等仍然会存储在系统共享的表空间中。

Innodb存储引擎中，和达梦类似的是，一张表也会分为两个段，其中一个段是叶节点段，存储实际的数据，另外一个段是索引段，存储索引的指针信息。而表中DML的UNDO信息会存储在rollback segment中。和Mysql Innodb不同的是，达梦使用全局ROLL表空间存储ROLL SEGMENT，而且整个ROLL文件中只有一个ROLL SEGMENT，所有UNDO记录通过链表的方式组织。

上面这张innodb的逻辑结构图画的十分清晰，所有的表的行数据是存储在extent中的（达梦称为（簇），而每个extent是多个连续的PAGE组成的，每个PAGE中存储了行数据。实际上这个leaf node segment和Oracle的TABLE SEGMENT是十分类似的，所不同的是多了一个Index segments。相当于在创建表的时候同时又默认创建了一个主键索引。Mysql在创建这个主键索引的时候，会区分不同的情况。如果要创建的表上没有设置主键索引，那么会选择表上的一个非空唯一性索引作为主键索引，如果不存在这样的索引，那么Mysql会使用一个六字节的唯一性自增值创建一个主键索引。

达梦数据库把这个索引称为cluster primary key，在创建表的时候可以指定。如果没有指定cluster primary key ，而数据库参数PK_WITH_CLUSTER被设置为1，则自动会把主键转换为cluster primary key，否则就会创建一个自增索引。

看到这里，可能有些朋友觉得自己看明白了，实际上所谓B树表只不过是一个索引段加上一个ORACLE 堆表的数据段而已，并没有太大的区别。实际上不是这样的，Oracle的堆表的数据写入是无序的，如果某些块没有写满，那么都可以插入新数据，数据插入的时候具有一定的随机性，并发插入的时候，可能先插入的数据被写在比较靠后的数据块中，从表中顺序扫描整张表，返回的数据是无序的。而B树表中的数据都是按照主键顺序排序的，是有序的，按照叶段的顺序扫描，返回的数据是按照主键排序的。

Mysql innodb等采用B树存储结构的存储引擎一般采用上图的模式，当数据被插入表的时候，会根据主键索引或者簇索引的指示插入到某个位置，而不会像Oracle那样，通过segment的free space bitmap寻找空闲位置插入。

Innodb的PAGE结构与达梦的有些类似，前面是FILE HEADER/PAGE HEADER，中间是数据记录，数据记录也是从低地址往高地址写，和Oracle相反。FREE SPACE后面是行记录指示器的数据结构，有指针指向某个具体的行，最后是一个8字节的PAGE尾部，主要用于校验，这也是达梦没有的结构。

Innodb的这种存储结构，并不存在一个十分友好的类似Oracle的记录物理地址的ROWID这样的结构。所以要想定位某条数据记录，需要使用主键或者簇主键的方式来实现。主键可以定义某条记录的唯一性地址，因此Mysql的某张表上的其他索引（secondary index）的索引中存储的键值不像Oracle那样存储ROWID就可以了，而是存储的是主键中这一行的地址指针。基于一个secondary index的查询首先找出某些行的主键，然后再去扫描一次主键索引，才能找到相关行的地址，再找到这条记录。比起有rowid的Oracle数据库，这里多了一次主键索引的扫描。

理解了上述结构以后，我们会发现虽然B树结构存储引擎实际上实现起来是类似Oracle的表上加一个主键索引。不过实际上的差异还是显而易见的。比如我们在Oracle数据库中大批量装载数据的时候，只会产生主键索引的叶节点分裂，存储的数据块不会分裂重组，而B树存储结构的表，索引段和数据段都会产生裂变重组，数据库脏块的数量会大幅增加。

另外一点大家比较容易想到的是对于主键键值的修改。在堆表中，修改主键键值只需要更新主键索引，而在B树存储模式下，这条记录也可能需要做存储位置的迁移。这无疑会降低此类操作的性能，同时会增加高并发下锁的开销。

不同的存储结构都各有利弊，并不能很直接的说哪种更好。不过在开发高并发，大数据量的系统的时候，了解存储引擎的一些特点，可以有效的避免一些问题。比如在Mysql、达梦等数据库中建表，尽可能定义一个显式的主键，从而避免系统自动添加主键。另外如果某张表的热块冲突特别严重的时候，主键可以考虑选择随机性的数据，而不是单边增长的数据，就可以有效的进行数据打散，降低热块冲突。

数据库

文章转载自白鳝的洞穴，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

B树结构表是什么意思

评论