David, Jared,
I will try to answer point 2 regarding the structure of the index.
David, your assertion on the page splitting and the levels of an index or what I call the depth of the index tree is not correct (all of the leaves are ate the sale level). Let me explain in more details but not too much detail since it will be long to explain here in an answer.
Informix uses a B-TREE structure for its indexes on most indexes that we use, or more precisely a B+TREE. A BTREE or a B+TREE by definition has a BALANCED (B in BTREE) tree structure at all times meaning all of the leaf nodes are on the same level or the same depth. No matter what key value you are trying to locate in a index, the engine uses the same number of disk accesses since you have the same number of levels for all of the keys stored in a node (a disk page). That is one of the important features of a B+TREE used by the Informix engine. A key value is stored in a leaf node (page) but the same value can also be present in the higher level nodes to allow the engine to decide in which node page the value is located. Informix does not use BTREEs but B+TREEs.
The difference between BTREE and B+TREE is that the B+TREE contains ALL of the keys (together with their ROWIDS) in the deepest level or the highest level and all of the nodes (pages) at the highest level are linked together in both directions to allow scans in both directions since the data is always sorted; in order to allow clauses in the WHERE clause of a SELECT such > n to scan from left to right and < n to scan from right to left without having to go up a level of the tree and descend to the following page (saving disk accesses).
When a page (node) is full, it is split in half and the middle (pivot value) value gets bumped up to the higher level node if the page split contains an odd number of values and if the number of keys is an even number, it bumps up the higher value of the first half of the values. The engine continues to add pages at the same level until the upper node is full and so on.
It is impossible to have 5 levels in one section of the B+TREE and 4 levels in another section of the B+TREE (index structure). As a matter of fact, there is one single statistic generated by UPDATE STATISTICS and stored in sysindices (sysindexes view) per index. The highest level of any index is 20 in Informix. This will theoritically allow a humongous number of rows; never seen it myself. Most of the large database that we know have 5 or 6 levels or may be 7 (rarely); it is exponential. A table will have a large number of levels in a index if the table is indeed large or very volatile (a lot of holes after deletes and updates). That is why recreating indexes sometimes can save levels and hence disk accesses. Going from 5 levels to 4 saves 1 disk access or 20% of the index disk accesses. What I would suggest is to may be use a larger page size to store more keys in an index page and lower the levels. For large indexes, go yo 16K pages for the index.
oncheck -pT database:tabname will not only give you the levels per index for that table but also the average number of free bytes at a level
Jared, going to a sixth level made you need mode disk space since the engine needs to keep the B+TREE balanced at ll times even if the pages contains a lot of holes. Of course, what you did (redreate the index) saved you levels and disk space since your new inex structure is clean (a lot less holes). So what you observed is normal.
This is the same for mono-column indexes or composite indexes.
I hope that this helps inderstand the index structure functionning and why you faced the space issue.
Cordialement, Regards, Khaled Bentebal Directeur Général - ConsultiX Tél: 33 (0) 1 39 12 18 00 Mobile: 33 (0) 6 07 78 41 97 Email: khaled.bentebal@consult-ix.fr Site Web: www.consult-ix.fr
Le 01/03/2023 à 23:07, David Williams via IBM Community a écrit :
010001869f374d82-ec14d26a-33fc-4e98-9d75-1d7b13cc921a-000000@email.amazonses.com"> I am not sure it will always merge all pages, it is more focused on removing deleted entries from pages e.g. it will only look at pages with... -posted to the "Informix" group
Subject: RE: Index shrinks an entire b-tree level when removed/rebuilt....
2. If in a part of the index a page becomes full and a new row needed to be inserted the page will be split and another level created. The level does not have to be the same in all branches of an index.