深入浅出Linux之内核数据结构(2)

图中显示,元素空间总共为256,但元素个数不固定。那么如果用数组存储,好处是插入查找只用一次操作,但是存储空间需要256,这是不可思议的。如果用链表存储,存储空间节省了,但是极限情况下查找操作次数等于元素的个数。而采用一颗高度为2的基树,第一级最多16个冗余结构,代表元素前四位的索引。第二级代表元素后四位的索引。那么只要两级查找就可以找到特定的元素,而且只有少量的冗余数据。图中假设只有一个元素10001000,那么只有树的第一级有元素,而且树的第二级只有1000这个节点有子节点,其它节点都不必分配空间。这样既可以快速定位查找,也减少了冗余数据。

基树很适合存储稀疏的数据,内核中文件的页cache就采用了基树。关于基树的文章很多,读者可以结合代码分析一下。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/22849.html