索引组织表

索引组织表与堆表

  在上一章的学习中我们讨论了存储I/O的影响，提出了贴合存储I/O的优化方向，并由此引申出索引的原理，集合两者思想的B+树的数据结构，我们了解B+树通过内部节点仅存储键值对来导航，叶子节点存储全部数据的方式，达到快速检索，数据集中存储等优势。
  其实综合来看，B+树的数据结构也适合表数据的物理存储格式，当我们把表中的某一列数据当作索引来看待，比如说主键，那么其余的列数据其实就可以作为完整数据来放到叶子节点中去，以这种存储格式的表我们称之为索引组织表（IOT）。
  在DM8中，普通表、分区表默认存储格式都是索引组织表，当建表过程没有指定聚集索引时，会通过伪列phyrowid来进行索引组织存储。
  而市场上主流的关系型数据库中，MySQL（InnoDB）默认采用索引组织表，Oracle、SQL Server 和 DB2 虽支持索引组织表但默认使用堆表，PostgreSQL 则仅支持堆表，不支持索引组织表。
  堆表格式中数据为无序存储的，数据和索引分开存储，主要通过索引来进行数据位置定位。堆表和索引组织表的差异对比如下（以下描述的主键一般指聚集索引键）：

  从对比可以看出，索引组织表和堆表各有优点，索引组织表更适合读多写少、查询以主键/索引键为入口的业务，堆表更适合写多读少、写入热点分散、需要高并发批量插入的业务。

DM8索引组织表在3层B+树的探讨

粗略估算

  在上一篇中，我们学习B+树的过程讨论了3层B+树下索引键值行数量的最多存储值，那近3亿的值属于理想值，至于索引组织表的存储数据数量必定不一样，但也可以同样讨论一下，基于以下条件设定：

1. 达梦中都是推荐页大小为32KB，所以设定叶子节点大小为32KB，填充因子默认100%，但是仍然需要考虑保留少量空间用以其他维护信息记录，这里我们设定叶子节点可以利用为31KB；
2. 为了方便计算，把每行数据的大小设定为1KB；
3. 聚集索引键为bigint的rowid，8B大小；
4. 基于上一篇的讨论，聚集索引键值大小仍为16B，于是计算3层B+树的索引组织表最大行数如下：

  根结点（第一层）：最多可以存储的键值对数量为32768 / 16 ≈ 2048 个。
  中间节点（第二层）：每个中间节点最多也可以存储 32768 / 16 ≈ 2048 个键值对，于是根据根节点得到的子树数量，第二层最大键值对数量是：2048x2048≈4,194,304个。
  叶子节点（第三层）：每个叶子节点最多行数据为
31744 / 1024 ≈ 31行，那么总的叶子节点数量为 4,194,304 × 31 ≈ 130,023,424行数据。
  通过以上的粗略计算评估，我们可以预估在DM8的3层B+树索引组织表，如果表行数据在1KB，那么最多存储行数为130,023,424行，当然这是粗略计算值，实际设计中不可能把根节点、第二层节点都完全填充满。

模拟验证

  DM8中可以在收集表统计信息后，通过SYSSTATS视图来确认表的B+树深度，所以我们可以模拟测试不断写入数据来确认一下3层变化到4层时，实际容纳了多少行数据。
  我们先创建一张测试表，表中数据列均使用定长字符串，尽量保证每行数据总长在1KB左右（预留了17B，根据指针和聚集索引键大小预留）。

CREATE TABLESPACE TEST20250609 DATAFILE 'TEST20250609.DBF' SIZE 1024;
CREATE TABLE TEST_BTREE
    (   C0 CHAR(7),
        C1 CHAR(100),
        C2 CHAR(100),
        C3 CHAR(100),
        C4 CHAR(100),
        C5 CHAR(100),
        C6 CHAR(100),
        C7 CHAR(100),
        C8 CHAR(100),
        C9 CHAR(100),
        C10 CHAR(100)
 ) STORAGE(ON "TEST20250609", CLUSTERBTR) ;

  接着我们通过以下语句，来实现批量数据写入，第一次我们先写入20行数据。

DECLARE
v_str varchar(150);
BEGIN
      FOR i in 1..10 LOOP
           EXECUTE IMMEDIATE 'select DBMS_RANDOM.STRING(''a'',130);' into v_str;
		   FOR i in 1..2 LOOP				      
		      insert into TEST_BTREE select substr(v_str,0,7),
		      substr(v_str,1,100),
		      substr(v_str,2,100),
		      substr(v_str,3,100),
		      substr(v_str,4,100),
		      substr(v_str,5,100),
		      substr(v_str,6,100),
		      substr(v_str,7,100),
		      substr(v_str,8,100),
		      substr(v_str,9,100),
		      substr(v_str,10,100) from dual;
		   end loop;
		   commit;
     end loop;
end;

  写入后数据，我们再通过STAT函数更新测试表的统计信息，最后查询SYSSTATS视图确认B+树层树，如下图3.1，BLEVEL的值为0，表示当前B+树深度为第1层。

第1层最大行数

  我们继续写入数据，并同步更新统计信息确认B树深度，经过不断测试验证，最终确认此B+树的第1层最多可以容纳1KB左右数据为31行。如下图3.2，在31行数据时，仍为1层：

  写入第32行后，B+树分裂，变化为2层，图3.3：

第2层最大行数

  在上面我们测试过程可以发现，根节点对于32KB的数据页利用其实只能有31KB，于是基于此我们计算第2层最大行数应该是在31744/16*31=61504行左右。实际测试验证后，得到结果如下图3.4，在53630行时，B+树仍为2层：

  写入第53631行后，B+树分裂到第3层，图3.5：

  此时表大小应该是在53631KB/1024≈52.37MB，从视图信息看在54MB左右，是因为数据库是按簇大小进行分配了，而当前簇大小是32KB*16=512KB，在预分配的策略下会看到视图计算的大小比实际大小略大一点（图3.6），符合我们平均行大小1KB设计。

第3层最大行数

  在第2层测试验证中，不难看出预估结果和实际结果已经有较大偏差了，实际值53630/预估值61504=0.8719758064516129，但是仍然可以提供一个大概的预估范围以方便我们继续进行测试下去，基于第2层预估和实际结果偏差值，我们预估第3层行数为1984x1984x31x0.8719758064516129=106,401,920左右，此时行数已经达到亿级别了，如果按此行数计算表大小会达到101GB以上。
  为了得到准确结果，我们继续进行模拟测试验证，最终得到测试结果如下，在第103017309行时，我们B+树仍为3层：

  而写入第103017310行后，B+树最终分裂到了第4层了：

小结

  通过以上模拟，我们得出一个参考的粗略结论来，在达梦的索引组织表中，假设每行数据为1KB左右时，构造表的B+树在第1层时可以容纳最多31行数据，在第2层时可以容纳最多53630行数据，而第3层时可以容纳最多103,017,309行左右数据，当超过此行数B+树会分裂为4层B+树。
  从原理角度看4层B+树相对于3层B+树会多了1层I/O代价，所以当数据规模足够多的 时候，就要考虑设计分区表来使用。
（注：以上模拟测试是特定条件下测试结果，仅供参考，理论上使用变长字符、每行不满1KB的情况下，3层B+树索引组织表可容纳的数量会更多）