idr 图示

看了idr的源码,思想基本同基数树一致,在网上找了几副图:

图片引用自:http://blog.csdn.net/yyttiao/article/details/8164029

pre_get:

单层情况下的布局:

在idr.layers == 1 的情况就是上面这图所示,所有的ptr都落在ary对应的地址区域...而对应得到的id值就是0到31.也就是5位..用4字节的低5位表示0到31 这32个地址对应的区域..下面再看下2层的情况

从前副图中,我们总结下..在1层中,id最大值为1 << 5(32只需要5个二进制位) * 1 =  在2层中1 << 5(32只需要5个二进制位) * 2  在2层的情况中,仅仅覆盖了4字节中的32^3次方 32768 个id号..所以这颗树可以继续增长..直到4字节的最大值

原文地址:https://www.cnblogs.com/openix/p/2890309.html