a radix tree is a practical mean to store sets of integers , particularly when they are written at a same length . when one uses integers , it is clearly always possible to impose them a common length of writing ( the one of the longest or more ) by completing their writing with a adequate number of digits leftmost 0 . let us for instance consider a set of integers that we write on a common length in basis 2 , s ={ 0 , 2 , 5 , 7 , 11 }={ 0000 , 0010 , 0101 , 0111 , 1011 }. one may then store this set in a radix tree whose paths from the root to the leaves , represent the writing of the integer stored in the leaf of the tree . for instance , the preceding set may be stored in the radix tree of fig1 . the advantages to use a radix tree are numerous : the storage is cheap in terms of memory space because the common prefixes of distinct integers are stored only once . furthermore , as shall be seen in the next sections , the logical operations on such stored sets are fast , cheap in terms of machine resources and simple to implement . we detail how the radix trees may be useful and efficient to store the data of a data base or to modify it . in the first part , we suppose that the data base is composed of a single table , itself composed of a single column . then we will suppose that the data base is composed of a single table , itself composed of several columns and of at least a primary key . it may indeed be very useful to authorize a table to handle several primary keys . indeed , practically , it happens frequently that a line of a table is only partially filled . it may , then so happen that a primary key is incomplete , then unusable , but that another is complete . the last sub - part is dedicated to the creation of indexes of any data base . a primary key is a column , or a sorted set of columns , such that two different lines of the table could not have the same values one this ( or these ) columns . there exists however always an implicit primary key and very useful : the index of the line in the table ( it is indeed a primary key because two distinct lines may not have the same line index ). from now on , we shall suppose that this primary key is actual . if one has to store , examine or deal with a data base of a single table , itself constituted of a single column , one may compute the thesaurus of this column and for each word of this thesaurus compute the set of the lines indexes it appears at . these lines indexes may very naturally be stored in a radix tree . let us notice that during the creation of the thesaurus , a sort of the data is performed . we sort indeed the couples ( word , line index ) according to words and , when the words are equal , according to the lines indexes . thus one may on the one hand compute the thesaurus and on the other hand , for each word of this thesaurus , the radix tree of the lines indexes it appears at . ( male , 0 ), ( female , 1 ), ( female , 2 ), ( male , 3 ), ( female , 4 ), ( male , 5 ), ( male , 6 ), ( female , 7 ), ( female , 8 ), ( male , 9 ), ( male , 10 ) one may then build the thesaurus and , for each word of the thesaurus , the set of the lines indexes it appears at . the word & lt ;& lt ; female & gt ;& gt ; appears at lines { 1 , 2 , 4 , 7 , 8 } and & lt ;& lt ; male & gt ;& gt ; at lines { 0 , 3 , 5 , 6 , 9 , 10 }. after this work , it is very simple to answer questions like & lt ;& lt ; what are the line indexes the word & lt ;& lt ; male & gt ;& gt ; appears at ?& gt ;& gt ; but quite difficult to answer to a question like & lt ;& lt ; what is the content of the cell at line 5 ?& gt ;& gt ;. for this kind of request , one may result to the section 5 below . the sets of lines indexes may hence be stored in radix trees . this process of storage is very useful to compute the intersection , the union etc . . . of such sets . in the preceding example , we obtain the result presented fig2 . there is another common request which concerns the content of a column : the & lt ;& lt ; between & gt ;& gt ;: one may wish to know the lines indexes whose content values is between two bounds . let us suppose for instance that a column contained dates , written at the format yyyymmdd . comparing two dates stored at this format is actually the same thing than comparing them lexicographically . but we also may enrich the thesaurus of the words obtained as truncations of the words of the initial thesaurus . for instance , we may decide to enrich the thesaurus of all the truncations of the four or six first letters of the words of the initial thesaurus . thus each word would be represented , in our example , three times : a time as itself , a time truncated at six characters and a last time truncated at four characters . any word of six characters , say yyyymm , will appear each time the initial line value was yyyymmxx . in other words , the set of the lines indexes the word yyyymm will appear is the union of the sets of lines indexes where appear a word yyyymmxx ( which means yyyymm followed by anything ). in the same way , the word of four characters yyyy will appear each time a word like yyyyxxyy was present in the initial table . its radix tree is thus the union of the radix trees of the words it is prefix of . the point is that a clause & lt ;& lt ; between & gt ;& gt ; may be treated with an important saving of readings on the storage facility . for instance , if one looks for the set of the lines where appear a date between [ 19931117 , 19950225 ], the number of requested readings of radix trees is 14 + 1 + 1 + 1 + 25 = 42 ( because [ 19931117 , 19950225 ]=[ 19931117 , 19931130 ] u [ 199312 , 199312 ] u [ 1994 , 1994 ] u [ 199501 , 199501 ] u [ 19950201 , 19950225 ]), instead of 466 . it may sometimes so happen that some lines of a table are not filled . but in order to create radix trees , each line should have a value . one chooses in advance some values signifying that the corresponding line has no value . naturally , we shall choose a value related to the type of the stored data ; for instance , we may choose : # empty # for a string of characters , − 2 31 for a signed integer on 32 bits , 2 32 - 1 for an unsigned integer on 32 bits , − 2 63 for an signed integer on 64 bits , 2 64 - 1 for an unsigned integer on 64 bits and so on . . . as explained above , the storage of a column with thesaurus and radix trees is not very efficient to answer to a request like & lt ;& lt ; what is the value at line 17 ?& gt ;& gt ;, for instance . this is why it is necessary to store additionally the column in its natural order . of course , rather than storing the column itself , it will often be profitable to store the sequence of the indexes of the words in the thesaurus . we name the additional storage the un - reversed image of the column . for instance , the preceding column will be stored in the following way : it may so happen that , as the data base is transformed , a word appears in or disappears from the thesaurus ( for instance when one takes off or adds lines to the table ). one could then think that the complete rewriting of the column is necessary . it is actually not the case : rather than storing a sorted thesaurus , one may store , it unsorted and record on the side a permutation allowing one to find back the lexicographical order of the words composing it . this is why whenever a word appears in the thesaurus , the complete rewriting of the column is not necessary . we rewrite in this case the permutation allowing one to retrieve the lexicographical order of the words rather than the thesaurus itself . fig3 illustrates the summary of the complete storage of a column . when the data base contains a single table made of several columns , it may be treated as if it were constituted of independent columns . in other words , one may create the storage of each of the columns constituting the table . the only question remaining to be answered is then the treatment of the primary key . when one deals with a primary key , one needs to answer as fast as possible to questions of two opposite types : & lt ;& lt ; at which line may we find a given value of the primary key ?& gt ;& gt ; and & lt ;& lt ; what is the value of the primary key at a given line ?& gt ;& gt ;. one may efficiently answer to both of these questions by storing at once the column or the columns constituting the primary key in the order in which they appear in the table and a permutation allowing to read the columns in the order fitting any comparison function . one may then find back a given value by dichotomy . for instance , let us imagine that a primary key is formed of two columns whose values are stored in the array below . in this example , the indexes of the lines are again explicitly expressed but written between parenthesis . we hence store the two columns exactly as they are in the table and a permutation , fitting the comparison function we choose . for instance , we may decide to compare first the first columns lexicographically and in case of equality to compare the second as ordinals . taking off the values ( but keeping the indexes ) one obtains the permutation ( 7401632859 ). when one stores a table , it is very convenient to store and keep up to date the total number of lines it is made of . in a relational data base , there are usually several tables linked one to the other by sets of primary keys , foreign keys . as explained above , a primary key is a column or an ordered set of columns which cannot take the same values at two distinct lines . ( the line index is a basic example of primary key .) let us suppose that a table is constituted of several millions of lines but that some of its attributes could take only a few different values . ( for instance a data base containing genealogy data may contain the names of the persons , for each of them his birth country , his birth continent , the birth country and continent of his mother and first child if he ever exists . instead of filling all the columns , it is considered as very economical to store in such a case the countries in a table separated from the main table and the continents in a third table . the main table contains then at each line a value ( a foreign key ) giving a line identifier ( a primary key value ) of the & lt ;& lt ; country & gt ;& gt ; table and the table & lt ;& lt ; country & gt ;& gt ; contains , at each of its lines , a value ( a foreign key ) identifying one of the lines of the table & lt ;& lt ; continent & gt ;& gt ; ( primary key ). here is an miniature example (& lt ;& lt ; client & gt ;& gt ; table hereunder ) illustrating the above . ( in this example , & lt ;& lt ; cn & gt ;& gt ; designates the name , & lt ;& lt ; inc & gt ;& gt ; the income , & lt ;& lt ; bircoun & gt ;& gt ; the birth country , & lt ;& lt ; bircont & gt ;& gt ; the birth continent , & lt ;& lt ; mocoun & gt ;& gt ; the mother &# 39 ; s birth country , & lt ;& lt ; mocont & gt ;& gt ; the mother &# 39 ; s birth continent , & lt ;& lt ; eldcoun & gt ;& gt ; the elder child birth country and & lt ;& lt ; eldcont & gt ;& gt ; the elder child birth continent .) the set of the three tables occupies indeed less room than the initial table . but this illustrates also the idea that a relational data base may be transformed in a set of tables independent one from the others . in the preceding example , we may consider the table & lt ;& lt ; continent & gt ;& gt ; by itself , the table & lt ;& lt ; country & gt ;& gt ; with the table & lt ;& lt ; continent & gt ;& gt ; developed in it ( this means the table & lt ;& lt ; country & gt ;& gt ; in which the references to the table & lt ;& lt ; continent & gt ;& gt ; have been replaced with the lines of the table itself ) and the table & lt ;& lt ; client & gt ;& gt ; with the tables & lt ;& lt ; country & gt ;& gt ; and & lt ;& lt ; continent & gt ;& gt ; developed in it . it may obviously so happen , as in this example , that a given table could be developed several times in another . this means that a column of a developed tabled shall always be referred to as belonging to an expansion table via a set of primary and foreign keys which constitute the identity of the column . we hence define an expansion table as a table in which all the tables which could be developed in have been developed in as many instances than there exists sets of primary and foreign keys driving from the expansion table to the developed table . from now on , we consider that the relational data base is made of expansion tables , independent one of the other . for each of these expansion tables , on may build the indexes as explained in the case of a single table . we are now in position to examine and modify our data base so indexed . in this part , we shall explain how the created indexes may be used to solve efficiently sql requests . usually , a request involves several tables and may be split in two distinct steps : the & lt ;& lt ; where & gt ;& gt ; clause which asks the data base manager program to compute the line indexes of a table and the & lt ;& lt ; select & gt ;& gt ; clause , which asks to the data base manager program to perform computations on the data located at the computed line indexes . the first part may contain tables joints ( a link between a primary key and a foreign key ), a comparison between a column and a constant ( with an arithmetical connector like =,& gt ;=,& gt ;,& lt ;,& lt ;=, between , like , in . . . ) or a comparison between two columns ( same arithmetical operators or a cartesian product ). these requests are linked one to the other thanks to logical operators ( and , or , not . . . ). the second part of the request may contain arithmetical operations like sums , products , numbering operator *, and so on . . . as explained above , each of these tables is considered as an expansion table , which , means than the table joints are irrelevant for such a table . a request involves usually several tables . the tables involved in the request are all developed in a nonempty set , say t . a single of these expansion tables is not developed in the others . this table is the expansion table in which we should solve the request . the & lt ;& lt ; where & gt ;& gt ; clause contains hence some joint clauses related logically to the remaining of the request by the logical connector & lt ;& lt ; and & gt ;& gt ;. it is then enough to simply erase them by replacing the & lt ;& lt ; and & gt ;& gt ; clause by its other term . this means that we replace & lt ;& lt ;( joint and remaining )& gt ;& gt ; with & lt ;& lt ; remaining & gt ;& gt ; and this for all the joint clauses . let us see now how we deal efficiently with a & lt ;& lt ; where & gt ;& gt ; clause , its joint clauses having been erased . we call & lt ;& lt ; atomic request & gt ;& gt ; an indivisible portion of the & lt ;& lt ; where & gt ;& gt ; clause , which means a comparison which is the whole request of which is linked to the remaining part of the request thanks to & lt ;& lt ; or & gt ;& gt ; or & lt ;& lt ; and & gt ;& gt ; operators but without containing such operators itself . if a table t contains a column c an atomic request may be for instance t . c = 3 , t . c between & lt ;& lt ; high & gt ;& gt ; and & lt ;& lt ; medium & gt ;& gt ; or t . c like word %. this simplest case to deal with is when there is an equality between a column and a given value . it suffices to read the radix tree of the wanted value for the column of the request . the & lt ;& lt ; between & gt ;& gt ; clause is a basic example of atomic request . all the other atomic requests may be reduced to this case . it is for this clause that the macro - words were created . let us take back the example given in the section dedicated to the macro - words . this column has been generated by enriching the vocabulary of the truncations of its words of length 4 and 6 . if we look for the line indexes whose values are between [ 19931117 , 19950225 ], it suffices to split the interval in : [ 19931117 , 19950225 ]=[ 19931117 , 19931130 ] u [ 199312 , 199312 ] u [ 1994 , 1994 ] u [ 199501 , 199501 ] u [ 19950201 , 19950225 ]. the computation is then very simple : we read the radix trees of the value 19931117 , that is united ( logical operator & lt ;& lt ; or & gt ;& gt ;) with the one of the value 19931118 , . . . which we unite with the one of the value 19931130 then with the one of the value ( truncated to 6 characters ) 199312 then with the one ( truncated to 4 characters ) of 1994 then with the one ( truncated to 6 characters ) of 199501 , then with the one of 19950201 then with the one of . . . 19950225 . so we are driven to read 42 radix trees instead of the 466 we should have had to read without the macro - words . one may of course treat half opened intervals by simply excluding the corresponding words . each of the atomic requests & lt ;& lt ; greater than or equal to & gt ;& gt ;,& lt ;& lt ; lower than or equal to & gt ;& gt ;,& lt ;& lt ; greater than & gt ;& gt ;,& lt ;& lt ; lower than & gt ;& gt ; is a hidden between clause . indeed if we call m and m the minimum and maximum values of the thesaurus of the concerned column , then the clause & lt ;& lt ; in & gt ;& gt ; is a way of mixing equalities linked one to the other thanks to & lt ;& lt ; or & gt ;& gt ; clauses . so we may manage them very simply . for instance t . c in ( a , b , c ) may be rewritten t . c = a or t . c = b or t . c = c . the management of the & lt ;& lt ; or & gt ;& gt ; clauses is explained below . the clause & lt ;& lt ; like & gt ;& gt ; is another example of a between clause . for instance , the clause t . c like mot % is indeed rewritten in t . c between [ mot , mou [. the atomic requests may be mixed thanks to logical connectors : the & lt ;& lt ; and & gt ;& gt ;, the & lt ;& lt ; or & gt ;& gt ; and the & lt ;& lt ; not & gt ;& gt ;. the three next sub - sections shall be dedicated to these operators . we wish to insist first on the fact that an atomic request always returns a radix tree , which shall also be the case for the logical operators and finally for the & lt ;& lt ; where & gt ;& gt ; clause . the fact to operate an & lt ;& lt ; or & gt ;& gt ; between two radix tree is actually the computation of their union . this computation may be very easily done by a simultaneous journey of these two trees . it is done recursively by : the & lt ;& lt ; and & gt ;& gt ; clause is computed almost the same way than the preceding one ( it corresponds to an intersection ): this clause demands nevertheless less computation time than the preceding one . indeed , when the two trees are read in parallel , it is sufficient that one of the two nodes does not have any left son for the exploration of the other left son to be useless . this is particularly true when the trees have been stored in hard drives in separated files . the & lt ;& lt ; not & gt ;& gt ; clause is one of the most difficult to perform among the atomic requests . it may however be treated quite easily . the maximal index of the lines of each table is stored and kept up to date . the clause & lt ;& lt ; nqt & gt ;& gt ; may then be treated as follows ( the goal is to compute the radix tree not t with t radix tree ). we define a full n - radix tree as a radix tree containing all the integer values for integers between 0 and n − 1 . to compute a & lt ;& lt ; not & gt ;& gt ;, it is then sufficient to erase recursively , thanks to an x - or , the leaves of t of a n - radix tree ( where n designates the maximal line index of the expansion table t belongs to ). when one takes off a node of a radix tree , one removes it and then removes recursively its father if it does not have any son left . for instance , fig4 shows the computation of not t when the expansion table t belongs to has amaximal line index of 13 . the initial tree is presented fig4 and the transformcdtree is presented fig5 . the comparison between two columns is the most complex of the atomic requests . this request is practically treated like a cartesian product ( see the next section ). let t be an expansion table and let t . c and t . d be two of its columns . a comparison between these two columns is an operation during which we wish to discriminate the lines of t such that t . c & gt ; t . d for instance . we emphasize the fact that is done at identical line indexes , this is what distinguishes this comparison from a cartesian product . let us denote by t c and t d the thesauruses of the columns t . c et t . d . we look for the lines such that at these lines , t . c & gt ; t . d . for each word of the thesaurus t c , we compute the radix tree r of the interval [ m 13 d , w ′] where w ′ designates the biggest word of t d lower than w . then by computing a & lt ;& lt ; and & gt ;& gt ; between r et and the radix tree of w , we obtain a radix tree t w . by computing the union of all the radix trees r w , we obtain the wanted radix tree . it is clear that the trees t w are not meant to be computed independently one from the others . since the words w are read in the lexicographical order , it is sufficient to unite t w to the tree corresponding to the addition of the words between w and the next word . one may also compute t c - t d thanks to the flat files and read the result . the other clauses are solved in a similar manner . ( for instance t . c & gt ;= t d ). indeed it may so happen that a clause & lt ;& lt ; where & gt ;& gt ; contains itself another clause & lt ;& lt ; where & gt ;& gt ;, correlated or not to the main clause & lt ;& lt ; where & gt ;& gt ;. an example of a correlated sub - request is given by the request # 17 of the tpc . this request is : in this request , one has to realize the computation of the sub - request , and take in account the requested conditions of the main request ( because the p_pankey of the sub - request belongs to the main clause & lt ;& lt ; where & gt ;& gt ;). so this kind of request may be rewritten in order to change this sub - request into a un - correlated sub - request . it suffices for such a purpose to duplicate the conditions requested by the main clause & lt ;& lt ; where & gt ;& gt ; into the correlated sub - request . in our example , this gives : finally , a correlated sub - request may be rewritten in a un - correlated sub - request . it is the subject of the next sub - section . a sql request containing un - correlated sub - requests may be treated by dealing first with the sub - requests recursively and by replacing in the request the sub - request by its result . from now on , we are able to deal with any clause & lt ;& lt ; where & gt ;& gt ; which returns a radix tree representing the set on the lines indexes of the expansion table matching this clause . let us suppose now that the purpose of the request is to perform some computations on some columns at the found lines . for instance one may want to compute the mean value at the found lines indexes of a given column . the values of this column are stored flatly in their order of appearance . it is then very simple to re - read the values of this column only at the line indexes found previously and to compute on these values the wanted computations . the embodiments described above are by way of example . it is clear that the man of the art is able to realize different versions of the embodiments without getting out the scope of this patent .