Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
 Re: Разбиение таблицы на несколько  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 31981
Exproment
в 99,9999% случаев это суррогатный ключ
Слишком много девяток :-)
7 сен 13, 23:26    [14809412]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
SERG1257
Member

Откуда:
Сообщений: 2877
Если СУБД не поддерживает секционирования, то ваш подход (секционированная вьюха) имеет смысл. Другой вопрос что в качестве поля для секционирования обычно выбирают дату.
Общая идея - вся работа с таблицей идет в фоновом режиме т.е. пользователям не видна, а затем раз DDL alter view и вуаля.
автор
я буду вынужден сначала их склеить union-ом
Скорее union all
автор
Вообще, какими подводными камнями это чревато (помимо умножения на 8 числа запросов)?
Запросы будут к объединяющей вьюхе. Повестьте на таблицу и вьюху ограничения, может оптимизатор догадается не трогать эти таблицы. (это надо проверять)
Надо смотреть на запросы. Особенно на DML. Если DML мало то это можно разруливать instead of триггером на вью.

Т.е. для примера

create view my_table as 
select * from current_table where my_date>'20130101'
union all
select * from table12 where my_date between '20120101' and '20121231'
union all
select * from table11 where my_date between '20110101' and '20111231'

alter table current_table add constraint ch_date check my_date>'20130101'
alter table table12  add constraint ch_date check my_date between '20120101' and '20121231'


Дальше проводишь заливку скажем в текущую таблицу. Таблица большая с ней идет постоянная работа.
делаешь ей копию
select * into my_table_copy from current_table и делаешь заливку уже в нее my_table_copy. Торопится не надо, индексов нет затем создаем индексы и раз - выгоняем пользователей, быстро переименовываем таблицы и вуаля можно запускать пользователей.
7 сен 13, 23:41    [14809435]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
Exproment
Member

Откуда:
Сообщений: 416
alexeyvg
ИД_ДатаВремя (данные заливаются по часам, то есть это ссылка на некую таблицу-календарь)
ИД_Счётчика
ИД_Объекта

Да, когда я вижу похожие решения то ничего против не имею. Особенно когда левое поле кластеризованного индекса является datetime, то это вообще прекрасно... Ибо великий бол регламентирует, что из кластеризованного индекса крайне производительная выборка по диапазону(никогда не понимал чем она отличается от выборки из некластеризованного), которую сложно представить по суррогату. Однако данное решение имеет место жить, если в таблице более нет полей и не появится, т.е. не будет необходимости строить другие некластеризованные индексы, иначе все три поля будут дублироваться на leaf уровне всех остальных индексов, увеличивая их ширину. Собственно я к сожалению никогда не могу гарантировать, что в будущем кто-нибудь не захочет расширить данную таблицу, потому избегаю таких решений. Меня смущает эта фраза:
alexeyvg
все остальные варианты не просто хуже, а вообще неработоспособны.

А чем вас не устраивает решение добавить identity ID, а данные три поля представить в виде некластеризованного индекса ? 0_о
alexeyvg
Слишком много девяток :-)

посчитаем, что клавиша залипла
8 сен 13, 00:01    [14809465]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 31981
Exproment
alexeyvg
все остальные варианты не просто хуже, а вообще неработоспособны.

А чем вас не устраивает решение добавить identity ID, а данные три поля представить в виде некластеризованного индекса ? 0_о
Пришлось бы купить второе хранилище для этого индекса, ведь его размер будет даже немного больше, чем у исходной таблицы.
Exproment
Особенно когда левое поле кластеризованного индекса является datetime, то это вообще прекрасно
Для datetime сиквел строит планы похуже, только int. В 2008 для схемы "звезда" появилась отдельная оптимизация плана, но работает она только для целых ИД.
Exproment
Ибо великий бол регламентирует, что из кластеризованного индекса крайне производительная выборка по диапазону(никогда не понимал чем она отличается от выборки из некластеризованного)
Если индекс не содержит всех нужных данных, то это же лукап, то есть несравнимо медленнее, в тысячи и миллионы раз. А если содержит, то это увеличение размера.
Exproment
Однако данное решение имеет место жить, если в таблице более нет полей и не появится, т.е. не будет необходимости строить другие некластеризованные индексы, иначе все три поля будут дублироваться на leaf уровне всех остальных индексов, увеличивая их ширину.
Ну да, нету индексов и не предвидится. Какие там ещё другие индексы на таблице фактов, она же примитивная, а все выборки по диапазону для агрегирования.
8 сен 13, 01:26    [14809648]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
Гость333
Member

Откуда:
Сообщений: 3683
MasterZiv
Поиск по индексу — это бинарный поиск, найди в википедии

Местные бэтмены настолько суровы, что ищут в индексе (т.е. B+-дереве) при помощи бинарного поиска.
ТС, не слушай этого дядю, он плохому научит
9 сен 13, 09:39    [14812119]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34705
Гость333
MasterZiv
Поиск по индексу — это бинарный поиск, найди в википедии

Местные бэтмены настолько суровы, что ищут в индексе (т.е. B+-дереве) при помощи бинарного поиска.
ТС, не слушай этого дядю, он плохому научит


А ты как ищешь в дереве, гостюшко особо умный?
Давай поведай нам, поржать-то охото...
9 сен 13, 09:53    [14812173]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
aleks2
Guest
Гость333
MasterZiv
Поиск по индексу — это бинарный поиск, найди в википедии

Местные бэтмены настолько суровы, что ищут в индексе (т.е. B+-дереве) при помощи бинарного поиска.
ТС, не слушай этого дядю, он плохому научит


Не, слушай, ты скажи как?
Я тож интересуюсь повышением свово образования...
9 сен 13, 09:54    [14812177]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34705
andy_111
Спасибо, я примерно понял - единого решения не существует, надо пробовать. Замкнутый круг получается - чтобы быстро найти вставляемые данные, нужен кластеризованный индекс по указанным ключевым полям (я его сношу перед вставкой), но при самой вставке этот индекс реально замедляет процесс - это проверено на практике, с ним вставка получается медленнее в несколько раз.


Нужен, во-первых, ЛЮБОЙ индекс по полям поиска, не обязательно кластерный.

Во-вторых, он нужен только на момент выделения записей, которые нужно вставить,
перед самой вставкой этот индекс можно и удалить.

В третьих, при вставке индекс не может так уж сильно тормозить вставку, возможно, там у тебя ещё что-то вставку тормозит,
проверяй.
9 сен 13, 09:57    [14812195]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
Гость333
Member

Откуда:
Сообщений: 3683
MasterZiv
Гость333
пропущено...

Местные бэтмены настолько суровы, что ищут в индексе (т.е. B+-дереве) при помощи бинарного поиска.
ТС, не слушай этого дядю, он плохому научит


А ты как ищешь в дереве, гостюшко особо умный?
Давай поведай нам, поржать-то охото...

Открой столь рекомендуемую тобой википедию да посмотри, что такое бинарный поиск и что такое B+-дерево.
9 сен 13, 10:19    [14812322]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
aleks2
Guest
Гость333
Открой столь рекомендуемую тобой википедию да посмотри, что такое бинарный поиск и что такое B+-дерево.

Поведай нам, o великий гуру, тонкую разницу!
9 сен 13, 10:22    [14812342]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
Гость333
Member

Откуда:
Сообщений: 3683
aleks2
Гость333
Открой столь рекомендуемую тобой википедию да посмотри, что такое бинарный поиск и что такое B+-дерево.

Поведай нам, o великий гуру, тонкую разницу!

Бинарный (он же двоичный) поиск, как следует из названия — это метод поиска путём последовательного разделения отсортированного набора данных на 2 равные части.

Каждый узел B+-дерева содержит ссылки на "чуть большее", чем 2, количество дочерних узлов. Методика расчёта содержится, например, в BOL, статья "Оценка размера некластеризованного индекса". Где-то встречалось "правило большого пальца", что для "среднестатистического" индекса на одной странице хранятся 300 указателей на дочерний уровень.

То есть там, где для 1 млн. записей бинарные бэтмены будут использовать 20 операций поиска, обычные люди обойдутся тремя операциями.
9 сен 13, 10:47    [14812536]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
aleks2
Guest
Гость333
То есть там, где для 1 млн. записей бинарные бэтмены будут использовать 20 операций поиска, обычные люди обойдутся тремя операциями.


С этого места подробнее!
А то у меня начинает складываться впечатление, что божественный гуру - банальный недоучка.

ЗЫ. Логарифм по основанию 2 не так уж сильно отличается от логарифма по основанию N.
9 сен 13, 11:41    [14812831]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
zxc1257
Member

Откуда:
Сообщений: 71
Гость333
aleks2
пропущено...

Поведай нам, o великий гуру, тонкую разницу!

Бинарный (он же двоичный) поиск, как следует из названия — это метод поиска путём последовательного разделения отсортированного набора данных на 2 равные части.

Каждый узел B+-дерева содержит ссылки на "чуть большее", чем 2, количество дочерних узлов. Методика расчёта содержится, например, в BOL, статья "Оценка размера некластеризованного индекса". Где-то встречалось "правило большого пальца", что для "среднестатистического" индекса на одной странице хранятся 300 указателей на дочерний уровень.

То есть там, где для 1 млн. записей бинарные бэтмены будут использовать 20 операций поиска, обычные люди обойдутся тремя операциями.


+100

пруфы

drop table tbl1;

create table tbl1(id int identity, data char(10));

;with
l0(n) as (select 1 union all select 1),
l1(n) as (select 1 from l0 t1, l0 t2),
l2(n) as (select 1 from l1 t1, l1 t2),
l3(n) as (select 1 from l2 t1, l2 t2),
l4(n) as (select 1 from l3 t1, l3 t2),
rt(n) as (select row_number() over (order by (select 0)) from l4 t1, l4 t2)
insert into tbl1(data)
select top(500000) cast(n as char(10)) as data
from rt

create unique nonclustered index idx_tbl1_id on tbl1(id);


Статистика по уровням индекса index idx_tbl1_id
index_levelpage_countrecord_countavg_record_size_in_bytes
0111550000016
12111511
21211


Содержимое блоков на разных уровнях

+ root page level 2 block


PAGE: (1:22454)


BUFFER:


BUF @0x0000000003DB0540

bpage = 0x00000000E2AF6000          bhash = 0x0000000000000000          bpageno = (1:22454)
bdbid = 5                           breferences = 0                     bcputicks = 0
bsampleCount = 0                    bUse1 = 42296                       bstat = 0xb
blog = 0x121215ac                   bnext = 0x0000000000000000          

PAGE HEADER:


Page @0x00000000E2AF6000

m_pageId = (1:22454)                m_headerVersion = 1                 m_type = 2
m_typeFlagBits = 0x0                m_level = 2                         m_flagBits = 0x8000
m_objId (AllocUnitId.idObj) = 101   m_indexId (AllocUnitId.idInd) = 256 
Metadata: AllocUnitId = 72057594044547072                                
Metadata: PartitionId = 72057594040156160                                Metadata: IndexId = 2
Metadata: ObjectId = 677577452      m_prevPage = (0:0)                  m_nextPage = (0:0)
pminlen = 11                        m_slotCnt = 2                       m_freeCnt = 8070
m_freeData = 118                    m_reservedCnt = 0                   m_lsn = (437:4912:81)
m_xactReserved = 0                  m_xdesId = (0:0)                    m_ghostRecCnt = 0
m_tornBits = 0                      DB Frag ID = 1                      

Allocation Status

GAM (1:2) = ALLOCATED               SGAM (1:3) = ALLOCATED              
PFS (1:16176) = 0x60 MIXED_EXT ALLOCATED   0_PCT_FULL                    DIFF (1:6) = CHANGED
ML (1:7) = NOT MIN_LOGGED           

DATA:


Slot 0, Offset 0x60, Length 11, DumpStyle BYTE

Record Type = INDEX_RECORD          Record Attributes =                 Record Size = 11

Memory Dump @0x0000000038B6A060

0000000000000000:   06010000 00985d00 000100                      ......]....

Slot 1, Offset 0x6b, Length 11, DumpStyle BYTE

Record Type = INDEX_RECORD          Record Attributes =                 Record Size = 11

Memory Dump @0x0000000038B6A06B

0000000000000000:   069fe603 00785d00 000100                      .Ÿæ..x]....

OFFSET TABLE:
Row - Offset                        
1 (0x1) - 107 (0x6b)           
0 (0x0) - 96 (0x60)                     



+ non leaf level 1 block

PAGE: (1:23928)


BUFFER:


BUF @0x0000000003D87080

bpage = 0x00000000E2F08000          bhash = 0x0000000000000000          bpageno = (1:23928)
bdbid = 5                           breferences = 0                     bcputicks = 0
bsampleCount = 0                    bUse1 = 42573                       bstat = 0xb
blog = 0xb212121c                   bnext = 0x0000000000000000          

PAGE HEADER:


Page @0x00000000E2F08000

m_pageId = (1:23928)                m_headerVersion = 1                 m_type = 2
m_typeFlagBits = 0x0                m_level = 1                         m_flagBits = 0x0
m_objId (AllocUnitId.idObj) = 101   m_indexId (AllocUnitId.idInd) = 256 
Metadata: AllocUnitId = 72057594044547072                                
Metadata: PartitionId = 72057594040156160                                Metadata: IndexId = 2
Metadata: ObjectId = 677577452      m_prevPage = (1:23960)              m_nextPage = (0:0)
pminlen = 11                        m_slotCnt = 545                     m_freeCnt = 1011
m_freeData = 6091                   m_reservedCnt = 0                   m_lsn = (437:4912:83)
m_xactReserved = 0                  m_xdesId = (0:0)                    m_ghostRecCnt = 0
m_tornBits = 0                      DB Frag ID = 1                      

Allocation Status

GAM (1:2) = ALLOCATED               SGAM (1:3) = NOT ALLOCATED          
PFS (1:16176) = 0x40 ALLOCATED   0_PCT_FULL                              DIFF (1:6) = CHANGED
ML (1:7) = NOT MIN_LOGGED           

DATA:


Slot 0, Offset 0x60, Length 11, DumpStyle BYTE

Record Type = INDEX_RECORD          Record Attributes =                 Record Size = 11

Memory Dump @0x0000000038B6A060

0000000000000000:   069fe603 00385d00 000100                      .Ÿæ..8]....

Slot 1, Offset 0x6b, Length 11, DumpStyle BYTE

Record Type = INDEX_RECORD          Record Attributes =                 Record Size = 11

Memory Dump @0x0000000038B6A06B

0000000000000000:   0660e803 00395d00 000100                      .`è..9]....

Slot 2, Offset 0x76, Length 11, DumpStyle BYTE

Record Type = INDEX_RECORD          Record Attributes =                 Record Size = 11

Memory Dump @0x0000000038B6A076

0000000000000000:   0621ea03 003a5d00 000100                      .!ê..:]....

Slot 3, Offset 0x81, Length 11, DumpStyle BYTE

Record Type = INDEX_RECORD          Record Attributes =                 Record Size = 11

Memory Dump @0x0000000038B6A081

0000000000000000:   06e2eb03 003b5d00 000100                      .âë..;]....

Slot 4, Offset 0x8c, Length 11, DumpStyle BYTE

Record Type = INDEX_RECORD          Record Attributes =                 Record Size = 11

Memory Dump @0x0000000038B6A08C

0000000000000000:   06a3ed03 003c5d00 000100                      .&#163;&#237;..<]....

..............................................................................


Slot 543, Offset 0x17b5, Length 11, DumpStyle BYTE

Record Type = INDEX_RECORD          Record Attributes =                 Record Size = 11

Memory Dump @0x0000000038B6B7B5

0000000000000000:   06fe9e07 00f76100 000100                      .&#254;&#382;..&#247;a....

Slot 544, Offset 0x17c0, Length 11, DumpStyle BYTE

Record Type = INDEX_RECORD          Record Attributes =                 Record Size = 11

Memory Dump @0x0000000038B6B7C0

0000000000000000:   06bfa007 00f86100 000100                      .&#191; ..&#248;a....

OFFSET TABLE:
Row - Offset                        
544 (0x220) - 6080 (0x17c0)         
543 (0x21f) - 6069 (0x17b5)         
542 (0x21e) - 6058 (0x17aa)         
...
2 (0x2) - 118 (0x76)                
1 (0x1) - 107 (0x6b)                
0 (0x0) - 96 (0x60)               

<<<<



+ level 0 block

....

9 сен 13, 11:51    [14812884]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 31981
Гость333
aleks2
пропущено...

Поведай нам, o великий гуру, тонкую разницу!

Бинарный (он же двоичный) поиск, как следует из названия — это метод поиска путём последовательного разделения отсортированного набора данных на 2 равные части.

Каждый узел B+-дерева содержит ссылки на "чуть большее", чем 2, количество дочерних узлов. Методика расчёта содержится, например, в BOL, статья "Оценка размера некластеризованного индекса". Где-то встречалось "правило большого пальца", что для "среднестатистического" индекса на одной странице хранятся 300 указателей на дочерний уровень.

То есть там, где для 1 млн. записей бинарные бэтмены будут использовать 20 операций поиска, обычные люди обойдутся тремя операциями.
По моему, тут какая то путанница.
Может, MasterZiv и aleks2 имели в виду поиск значения на одной странице индекса? Хотя там такая структура, что проще перебрать и сравнить записи, а не городить бинарный поиск.
9 сен 13, 11:54    [14812906]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
zxc1257
Member

Откуда:
Сообщений: 71
aleks2
ЗЫ. Логарифм по основанию 2 не так уж сильно отличается от логарифма по основанию N.


тем не менее в страницах индекса не хранят только по две ссылки. потому, что логарифм этот только на бумажке. есть еще и время i/o
9 сен 13, 11:54    [14812910]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
zxc1257
Member

Откуда:
Сообщений: 71
alexeyvg
Гость333
пропущено...

Бинарный (он же двоичный) поиск, как следует из названия — это метод поиска путём последовательного разделения отсортированного набора данных на 2 равные части.

Каждый узел B+-дерева содержит ссылки на "чуть большее", чем 2, количество дочерних узлов. Методика расчёта содержится, например, в BOL, статья "Оценка размера некластеризованного индекса". Где-то встречалось "правило большого пальца", что для "среднестатистического" индекса на одной странице хранятся 300 указателей на дочерний уровень.

То есть там, где для 1 млн. записей бинарные бэтмены будут использовать 20 операций поиска, обычные люди обойдутся тремя операциями.
По моему, тут какая то путанница.
Может, MasterZiv и aleks2 имели в виду поиск значения на одной странице индекса? Хотя там такая структура, что проще перебрать и сравнить записи, а не городить бинарный поиск.


возможно, при большом количестве строк в странице индекса, в пределах страницы ищут и не перебором. хз. слоты то в пределах страницы отсортированы по ключу. бывает что весь ключ фиксированной длины или его часть фиксированной длины хз....
9 сен 13, 11:58    [14812937]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
Гость333
Member

Откуда:
Сообщений: 3683
aleks2
А то у меня начинает складываться впечатление, что божественный гуру - банальный недоучка.

Для простоты соглашусь с тем, что выделено зелёным, и не соглашусь с тем, что выделено красным.

Теперь, пожалуйста, охарактеризуйте того, кто говорит "значения в B+-дереве ищутся при помощи бинарного поиска".
9 сен 13, 12:13    [14813046]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
aleks2
Guest
Гость333
Теперь, пожалуйста, охарактеризуйте того, кто говорит "значения в B+-дереве ищутся при помощи бинарного поиска".


Он говорит правильно. Не вдаваясь в ненужные и несущественные детали.
9 сен 13, 12:17    [14813070]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34705
У, как у вас тут интересно...
9 сен 13, 12:28    [14813136]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34705
alexeyvg

По моему, тут какая то путанница.
Может, MasterZiv и aleks2 имели в виду поиск значения на одной странице индекса? Хотя там такая структура, что проще перебрать и сравнить записи, а не городить бинарный поиск.


Нет, никакой путаницы нет.
Мы имели в виду поиск в дереве индекса вообще. Он по сути ест бинарный поиск, и про стоимости, тоже.

Он конечно же N-арный в реализациях в СУБД, что добавляет ему немного скорости, но стоимость все равно остается O(log T), где T - количество записей в таблице.
Меняется только основание логарифма.
Не 2, а больше. Но точно основание это для индексов в бд и не определить, потому что число записей на разных страницах индекса разное, да и смысла в этом нет, поскольку основание логарифма — лишь коэффициент при логарифме, если приводить к одному основанию. А под O()
коэффициенты выбрасываются, они не имеют значения.

Кстати, B+ tree и называется именно так, потому что подъузлов у страницы индекса 2 или более.

Так вот, я и говорю,
Товарищь хочет уменьшить число записей на один порядок. Из под логарифма выйдет коэффициент, и удалится, скорость работы не поменяется.

Ему надо на 3-5 порядков уменьшить число записей в одной таблице, чтобы результат ощутить. Но в его положении на 3-5 порядков увеличиться и число запросов. :)
9 сен 13, 12:48    [14813249]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
Гость333
Member

Откуда:
Сообщений: 3683
MasterZiv
Кстати, B+ tree и называется именно так, потому что подъузлов у страницы индекса 2 или более.

Буква B в данном случае означает не Binary, а Balanced...
9 сен 13, 12:52    [14813270]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
zxc1257
Member

Откуда:
Сообщений: 71
[quot MasterZiv]
alexeyvg
Он конечно же N-арный в реализациях в СУБД, что добавляет ему немного скорости, но стоимость все равно остается O(log T), где T - количество записей в таблице.
Меняется только основание логарифма.


Вместо log2(N) прочитать logZ(N) блоков.
9 сен 13, 13:22    [14813568]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
invm
Member

Откуда: Москва
Сообщений: 9836
Строго говоря, бинарный (двоичный поиск) к деревьям вообще не относится. Господа aleks2 и MasterZiv, просто путаются в терминологии, подразумевая под бинарным поиском упорядоченный обход дерева.
9 сен 13, 13:52    [14813866]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
взгляд со стороны + wikipedia
Guest
invm
Строго говоря, бинарный (двоичный поиск) к деревьям вообще не относится. Господа aleks2 и MasterZiv, просто путаются в терминологии, подразумевая под бинарным поиском упорядоченный обход дерева.


A B+ tree can be viewed as a B-tree in which each node contains only keys (not pairs), and to which an additional level is added at the bottom with linked leaves.
B+ tree

In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children.
B-tree

In computer science, a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:[1]

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
The left and right subtree must each also be a binary search tree.
There must be no duplicate nodes.

Average Worst case
Space O(n) O(n)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)

Binary search tree

вроде как ни крути, а все свелось к binary search tree,
Гость333 педантично указал, что 2 и некое произвольное число не есть одно и то же
(ну и вообще, для кого пишут-то: B-tree, Not to be confused with Binary tree),
aleks2 и MasterZiv прицепились, что принцип все равно тот же и время логарифмичесткое.

а весь сыр-бор из-за того, что Гость333 ни разу не хам, в отличие от aleks2 и MasterZiv.
поэтому "война миров" неизбежна
9 сен 13, 14:18    [14814061]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение таблицы на несколько  [new]
vi0
Member

Откуда:
Сообщений: 296
Мартин Грабер "Mastering SQL"

К сообщению приложен файл. Размер - 126Kb
12 сен 13, 20:49    [14833500]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
Все форумы / Microsoft SQL Server Ответить