Indexing - comparison of tree structures
Started by Sascha Kuhlover 6 years ago6 messages
Hi,
I compared two data structures realistically by time, after estimating big
O. T-tree outperforms b-tree, which is commonly used, for a medium size
table. Lehmann and Carey showed the same, earlier.
Can you improve indexing by this?
Understandably
Sascha Kuhl
Attachments:
Just another bit faster.pdfapplication/pdf; name="Just another bit faster.pdf"Download
%PDF-1.5
%����
10 0 obj
<< /Linearized 1 /L 97607 /H [ 761 146 ] /O 14 /E 64465 /N 3 /T 97280 >>
endobj
11 0 obj
<< /Type /XRef /Length 58 /Filter /FlateDecode /DecodeParms << /Columns 4 /Predictor 12 >> /W [ 1 2 1 ] /Index [ 10 25 ] /Info 21 0 R /Root 12 0 R /Size 35 /Prev 97281 /ID [<71fbe5c19210f1b14673d4fa13116014><71fbe5c19210f1b14673d4fa13116014>] >>
stream
x�cbd�g`b`8 $���X�@�q�x$����"�l=�|b�201r�)f`�� �PV
endstream
endobj
12 0 obj
<< /Pages 28 0 R /Type /Catalog >>
endobj
13 0 obj
<< /Filter /FlateDecode /S 54 /Length 68 >>
stream
x�c```a``����� ��A�
�lf ����������a"v(f` �����0)�7Cs% J��
endstream
endobj
14 0 obj
<< /Contents 15 0 R /MediaBox [ 0 0 596 843 ] /Parent 28 0 R /Resources << /ExtGState << /G3 22 0 R >> /Font << /F4 23 0 R /F5 24 0 R >> /ProcSets [ /PDF /Text /ImageB /ImageC /ImageI ] >> /StructParents 0 /Type /Page >>
endobj
15 0 obj
<< /Filter /FlateDecode /Length 4444 >>
stream
x��]����}���s�h)^D t{���`�|@��@�
��������cWI�=��z�m�"YU�:u!�������������}�������������Oo���_���;�����]����=M����i���/o?�hN��g~���m�����o��|�������&5��|������e|�>}����3T����i74n0��������?)��(�����R�(e��������{\�>��gr���g,������o�_���nkL�����!)�l��o��&%T�(a|hk���e��O�](��u�Pb�@��.�N�'jL���~�����s)�c�m����������\�tp���V�>�����i��9��}�o�=KO�J{Y��O�}��L�n������m���5��[]��)j�3i�}�����i����y��0�0�-��� k����v�@�>��m��x�H�.&vEg#QtZ��#�
���?U37M������Qff�F��$����]2!'�m����������t����s-h}�my���-\���w��hK����[�X��MF+��EK�������n���Q�sr��n�����>_X��5������������=un`;p!t��k;Z����d���M�������0��^�$��z�a�n������GjG`@(�%�((��>P�5~\K�w����M���:B�t-��](���~T��>*H���������m�l����C��B�������h�����������C���L5n��n������c��n?6�QMz?�u���U@j��mp�
��U<�`>����V������
T����^
=��P�����z�J�OB����$��Y��;{WhQ�,�`)�`x�7��gI��=e�V�7yFE�>�Io�,&B�����~����.�QP�a ��B3]#Q�
=��K�
�F*��m7�3�m����`�ru�z�-
s��|�g�h�@"���[��9��f�!T�&��&�~9"E+� v���Y�a�X��m���)Ubb�Whb
T�X������u-����)��J�t�PD���ug��Z*�J����[��M�[�IZD��
#�t3!���*�3w+_��9�����X���sC`�|�F�����~9zw ��8���6�����}�}
����+�E'�q���bGB�U@�GEr���]q�E�D:��S��$U�:EB&NUT�2�!���B�k=���J�F���W��"@N���Xj�*R�H���eA��J���56�2��K�;��=�jc��r��KU�0��<t��:�-Mh��������Gt��P��� 0���fI�gJ��}��(��E�b#P`����q�]��E87������;��8.+wM�@Y����
��!���k�z��\�aZ�����
��!�)q��^n�����*o{��I���R�:�|��s"�/'�A.I-We�O���5
O��I �b�@d�����u��������wC�)Pu�a��+��D@&�K�9�>T$x(|a+�VU
�j��`������]���s���(�;�-� �vy�2���Ll��f�Z��uU���P4�q=���W������&R�u,�@��b��#�._B0w�r��Hc���
OY�/�����[w������
��}��l���I���j��F��}��V��VaB�~A��(i+��`q��@(��G�r<�U��x�}J+_ �FK��V:�cK�C��u��b�#rh��+�� t=}Wqt)x��#t
�4<,u`C�� �j��/��~�io/�.m//6�9s <a+�t;�Kw�sJ�u�����Q� r@�����Q�m��X��a����4� ��:����*G����Hq���a{B4�^���P��7G�-�d6�Vp����M;���
;x�g@�'TW�s��|d����qj_�O#W��O!V�V
��(u?��1����N�@
Sy<H������z��o��A~��9��3Bc����C��:��r���\������1��y��-*�~5����l*VA��S5�c�#< �'����jQ�g
���A��i>Ali�k)^������l�$L_���E�� ^���+c)j+��f����C7�.�1�~X9���+��Q�;"���Z���Fp����I/U���Kr9��wG��$$G�����0���P�X�p��a�������34kt���C0��j����Zq q���38T:�W���=�zu,�T*��S.4��R�;����j���mTuTJQ�(��jJO>z������R:��
5D���#��m���%�������I�y��I�WC��j�� j������g�y*E����4
%���������\�X�S��E���������b1�^��IzBe�3�����O��qB���R��`����O���}|Y,��,��� Mz�����|q9N�cG�(�c����{�������9��n������t2'��Q�������Qr�Q��$1��s�*:��"�V���Z��u�4���=3|�I�O��B~�4�{��S����e������U~����n����C�W�7�A���_����XC��8���+���3e�F���wg8��F��C1=y0ez��[>v��c�W}���b�x����PX� ?��UKO}:��Y�4q������b4��GB�?���X�����$?�_�Y+�S�e<?����Y����#��y�z�����-��������v�q���;f-}�_�����S�=a1D�o�$v��\���+���m��v;=���c}�KrJ&f�t�����_:��9]���#Q���p�����0����}>��B|8)D��&��[��>�G|�0��v�Z
iSc�m1������� ���<
�+\uS ����xC{d����P�������;�FW<�����O(����Y����[P���n��X����������[����k�Z ���B�`kD�CX#[���� LUc�V���O|#��a�L~��<��� z��!���`O����z�C!a
3����3=lz�]�]w�mG�6�z�����w��u�����t�)��5������T����M�O;��iqL���h�=^���D�{�~w�=.|?�3�������9]���~�g�|��ud��;��>��/?�2/�o��>��M�|��u��8���8G��<����'�=�y��m����,�'�[e�]������,�K��!.��^? �'q�$�%Oo&g_����x_�,�c����x��qM�-��5�L�:��|��[�bN���b�V����p ��3��/��`0���)/�b�[��S ��2�4<D��@BOH1�\r�>�`&���#)\\u:N��g�J�Q�����b�;��Z�W��ctD�]���b5�9��<�s�yi���Y�����������<�f�����>a����K���zq�F=����J�^-�.�T��L��R�s�\��Rpl�����z�}9&*}iNm��9?g57:�po�����B)������K6�%����I���p[��k���x���-��J��
�(����%t���q�_�\�X�3��s�����\R�q�S)�h'�}���3����d^?�XZ��T� �W�f(z9)�W.�R�0M���KAO���S�Tod�Gp-N�����8XU"������TB+ �^��V#��uO��=�{Y_��������t!%�S%�|� �]��-_�"��5��J��W�Roj�K�� \m��[f����P�J�c$�}�+�5��]o����4�����V��&b�(����/��-�R��V�$l:���6�����.��������<W9��n����;VxP=4���-Bj��9��-o��5f�=�����D�U����E�(��4��[��(�����R����}�����f8��
:��X7���LU���\P���Y|��4���&"��K=���@M�95�t�m��p���U��k�t���������[���xB�KE��j��/1�=�[+!j�^W����
�������{�m�� �%�3I�86M.�T��V�C$���"��U4�]k�)��?{������]���H����8O6n}[���Y�d���S��Fp8F����{ �H'�����L�9�r3����S��*f�v��%�nM�����d��{K���M�(�Bn(�t��H''B�E��sOb2��"�&���r��b1����v��Jc�0����Ob�m������|T�~n��d��;��{K��[��$Zdg�d+a���)�@�����t3���
S�
t��M�0����_�>��<4�Z�!L�������6hendstream
endobj
16 0 obj
<< /Filter /FlateDecode /Length1 60432 /Length 35865 >>
stream
x���y|��?|���g&�d&�l����2Y�l�H'$a HX%H$a_%aS%.�\ �
���"��^EE���WH2���������������4�:�W��S���� @ ���o�����_���)@T�������� ��P�6�v������ H6�s&�X0)���/ F����2�f��m��b�/"r�`FTr�~��E$L�9���wf�� ��3f���E�� J�`���57��.�o�r��7�����Gp� �@���������W ����N?�����w��
��6���2�Nw�j�s�W������`}�T�P��(�k�X�1T����#&���"P�Ca�{8.*��8^�v�8�J`� �F����~R��:�e����p'���
���^�� � R�v�8�(�@�B���G����[ cT�C��&����D��K�R�9��x?����X<�`��e��x��f�+^���J���n�cyoL�""U+��T���|3����i9{��k�'���y����e8��10�{!������c<���7C�b��y���9N��hLS^��"����g2��X����};�����
���=w��?��_����r�����^�����Y��V�w����=�e��_0�����C� X��~@� �����9���L�F��G�nvd,�JkPn&@o�
r��-/��/�/�q��\�P��0���
_��2���/� y�k_����G5Nc}8����������<��NFvl���b���9(#&���+2�mx{���\�+2������B��t!�
��Q�0 �#��k{� �u��X�o�y��e��&�.���<)2��q���Xp�l��`)"�*��������|�|/���lq���X� �=���'����KLU�V� ���h2�}N���C2��\f�����J�~�{��v���Oe� e�!����{���E�n,(��B7�����?�H�#�+{�'�A8IU��T\K�w�����P&�����K���S�a�Q��V�Jo�+~9�#��`���������X�
�0��x8�}�Q}O|{��&D="E�%k��I�j�Qn�"f 2��2t�C���;7����3����1��������a\G�~wr����^��?�����B���O(��.�����qe_�N({2/�����������%���1��^&������'���Q./���v�-��}�mb�Y��_��#����9,k���Gz��3�B� U��{0�k_#�!�X�j�A=�������1���1l@`��.i �_�41�������N]f�:K9��� ��9��������Sa���s4J9?������2���}��`��D<����p[�p_�|��!�LPC�u� ���>d�*:��u@%�����3�H!N,�rlJ�R���/ (�\��4�U�^�k/�-"Q���H���r�nE������<<W�/�"
��:n��L�~����gso��4T�Y��&+p^ y�f�����X� _�qd�G����k���c���q�"�K��J������%�eSL+g�B�+��"�<3�Z���eX�dH�\XV
il3�3��<����s��cc~Y�}�������H�{��A9o�|Fy;6~&�G��=H�;����4E��2����R��G`�R6Z�>���L�v ���'q��������u<{�>