1

Topic: bw-tree - As at division we transfer keys to the new?

Bw-tree Is such piece: it is invented in microsoft in 2013. https://www.microsoft.com/en-us/researc … ree-for... The Question about division . Is  P which shares. At division P, we create new  Q, there we merge from  P all keys> = kkk (a dividing key).  Q it is generated and there comes time moment (1). Further we climb in  P to add delta-redirect-kkk-to-Q. It happens at the moment of time (2). Between the moments (1) and (2) other flow was in time  in  P keys> = kkk. After (2) there is a situation that for> = kkk all walk in Q, and the part of keys> = kkk there is not present. How to be? By search to check both? Still a variant: at setting delta-redirect-kkk-to-Q in  P to put this delta through CAS it is not simple concerning current state P, and concerning that state P which was at the moment of the beginning of copying of the data in Q. Then if between (1) and (2) who-from changes P, the delta will not be interposed also we again we launch formation Q anew. But here risk: If actively flow INSERT in P state P will be constant new and the cycle of attempts of formation Q will do  iterations. Dug out pair of projects  students with attempts it  bw-tree, I esteem source codes even more in detail though they have stubs to addition TODO.

2

Re: bw-tree - As at division we transfer keys to the new?

Hello, pkl, you wrote: pkl> Bw-tree is such piece: it is invented in microsoft in 2013. https://www.microsoft.com/en-us/researc … ree-for... pkl> the Question about division . Is  P which shares. At division P, we create new  Q, there we merge from  P all keys> = kkk (a dividing key).  Q it is generated and there comes time moment (1). Further we climb in  P to add delta-redirect-kkk-to-Q. It happens at the moment of time (2). Between the moments (1) and (2) other flow was in time  in  P keys> = kkk. After (2) there is a situation that for> = kkk all walk in Q, and the part of keys> = kkk there is not present. How to be? By search to check both? Still a variant: at setting delta-redirect-kkk-to-Q in  P to put this delta through CAS it is not simple concerning current state P, and concerning that state P which was at the moment of the beginning of copying of the data in Q. Then if between (1) and (2) who-from changes P, the delta will not be interposed also we again we launch formation Q anew. But here risk: if actively flow INSERT in P state P will be constant new and the cycle of attempts of formation Q will do  iterations. Dug out pair of projects  students with attempts it  bw-tree, I esteem source codes even more in detail though they have stubs to addition TODO. And Bw-tree it not "variety"  B-trees? When insertion/removal operation instantly do not lead to change of elements in a tree, and all is added in certain buffers which can be both for all tree and for separate , and at approach of the certain moment there is a merge of that in the buffer to that that in a tree, I am simple article read quickly and on a diagonal and I can be mistaken, but there too like was told that insertions/removals are saved, , and then the DBMS solves when all this business needs to be merged, and does it in a background and if it so that in "theory" when began the draining process, new insertions are simply added in the buffer and in  P other flow simply physically not "". There is still an interesting variety of trees for exterior storage, LSM trees are well ground under record, but is worse with reading.

3

Re: bw-tree - As at division we transfer keys to the new?

Hello, SL, you wrote: SL> Hello, pkl, you wrote: pkl>> Bw-tree is such piece: it is invented in microsoft in 2013. https://www.microsoft.com/en-us/researc … ree-for... pkl>> the Question about division . Is  P which shares. At division P, we create new  Q, there we merge from  P all keys> = kkk (a dividing key).  Q it is generated and there comes the moment of time (1). Further we climb in  P to add delta-redirect-kkk-to-Q. It happens at the moment of time (2). Between the moments (1) and (2) other flow was in time  in  P keys> = kkk. After (2) there is a situation that for> = kkk all walk in Q, and the part of keys> = kkk there is not present. How to be? By search to check both? Still a variant: at setting delta-redirect-kkk-to-Q in  P to put this delta through CAS it is not simple concerning current state P, and concerning that state P which was at the moment of the beginning of copying of the data in Q. Then if between (1) and (2) who-from changes P, the delta will not be interposed also we again we launch formation Q anew. But here risk: if actively flow INSERT in P state P will be constant new and the cycle of attempts of formation Q will do  iterations. Dug out pair of projects  students with attempts it  bw-tree, I esteem source codes even more in detail though they have stubs to addition TODO. SL> And Bw-tree it not "variety"  B-trees? When insertion/removal operation instantly do not lead to change of elements in a tree, and all is added in certain buffers which can be both for all tree and for separate , and at approach of the certain moment there is a merge of that in the buffer to that that in a tree, I am simple article read quickly and on a diagonal and I can be mistaken, but there too like was told that insertions/removals are saved, , and then the DBMS solves when all this business needs to be merged, and does it in a background and if it so that in "theory" when began the draining process, new insertions are simply added in the buffer and in  P other flow simply physically not "". There is still an interesting variety of trees for exterior storage, LSM trees are well ground under record, but is worse with reading. Basically it is reminded buffered b-tree, but by all devil in "" it bw-tree. The question very private, it concerned implementation subtleties bw-tree.