14S_B*Tree 인덱스 (by junkume) [2014.12.07]
B*Tree 인덱스
- B*Tree 인덱스는 데이터베이스에서 가장 일반적으로 사용되는 인덱스 구조며， 가령 숫자 컬럼에 인덱스를 가지고 있다면 개념적인 구조는 그림 11\- 1 처럼될것이다.
 |
Note
블록 레벨 최적화와 데이터 압축을 한 경우는 실제 데이터 블록 구조가 그림 11-1과는 다르게 생성된다.
- 트리의 최하위 레벨 블록은 리프 노드(leaf node) 또는 리프 블록 (leaf block)이라고 불리는데，모든 인덱스 키와 인덱싱되는 로우를 가리키는 rowid를 포함하고 있다.
- 내부 블록인 리프 노드 위의 블록은 브랜치 블록(branch block)이라고 알려져 있다.
- 브랜치 블록은 인덱스 구조를 이동하는 데 사용된다. 인덱스에 42라는 값을 찾고자 한다면 트리의 최상위에서 출빌F해서 왼쪽으로 이통한다. 블록을 조사해서 우리
가 필요한 블록을 찾아서 42부터 50 범위의 블록으로 이동한다. - 인덱스 리프 노드는 실제로 양 방향 linked list이다. 리프노드에서 시작점을 찾은다음에는값의 정렬된 순서로 읽어나가기만하면 된다.
where x between 20 and 30
- 오라클은 20 이상의 값중 가장작은 키 값을포함하는 첫 번째 리프블록을 찾은후에 30보다큰값을 발견할 때까지 수평 방향으로 리프 노드의 리스트를 읽어나가기만 하면 된다.
- B*Tree 인덱스에서는 유일하지 않은 엔트리는 존재하지 않는다. 유니크하지 않은 인덱스 (non-unique index) 에도 오라클은 인덱스 키 값에 추가적으로 rowid를 기타 컬럼으로 추가하게 되기 때문에 유일하게 된다.
- ex) 예를 들어 CREATE INDEX 1 ON T( X. Y)라는 인덱스는 개념적으로 CREATE UNIQUE INDEX 1 ON T{X, Y, ROWID)라고 볼 수 있다
- B*Tree 특성 중 하나는 모든 리프 블록이 트리 안에서 모두 통일한 레벨에 존재한다는 것이다. 어떠한 조건이라도 루트 블록부터 리프 블록까지는 동일한 숫자의 블록을 방문한다 인덱스는 높이가 균형적이라고 말할 수 있다. 대부분B*Tree 인덱스는 수백만 개 로우를 갖고 있더라도 높이가 2 또는 3 이 된다.
Note
- 오라클에서는 인덱스 루트 블록부터 리프 블록까지 이동하는 데 포함된 블록의 수를 확인할 때 두 가지 용어를 사용한다.
- 첫 번째는 HEIGHT다 이는 루트 블록부터 리프 블록까지 이동하는 데 필요한 블록 수다. HEIGHT 값은 ANALYZE INDEX (name) VALlDATE STRUCTURE 영렁어를 실행하여 통계정보를 생성하면 INDEX STATS 뷰를 통해 확인할 수있다.
- 다른 하나는 BLEVEL 이다. 이는 브랜치 레벨의 숫자고 HEIGHT 값보다 1 적다(리프 블록 수는 포함되지 않는다)
- BLEVEL의 값은 통계정보가 수집된 이후에 USER_INDEXES 와 같은 일반 딕셔너리 테이블에서 조회할 수 있다.
- 숫자 컬럼이 기본 키로 설정된 10,000,000개 로우를 가진 테이블이 있다고 하자
select index_name , blevel , num_rows
from user_indexes
where table_name = 'BIG_DATA'
INDEX_NAME BLEVEL NUM_ROWS
------------------------------ ---------- ----------
BIG_DATA_IDX 2 1000000
- BLEVEL 2는 HEIGHT 3을 의미한다. 리프 블록을 찾는 데 두 번의 1/0 결과적으로는 세 번의 1/0를 수행한다는 것을 의미한다. 그래서 주어진 인덱스 키 값을 찾는 데 세 번의I/0를 예상할 수 있다
select x from big_data where x = 42;
----------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
----------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 13 | 2 (0)| 00:00:01 |
|* 1 | INDEX UNIQUE SCAN| BIG_DATA_IDX | 1 | 13 | 2 (0)| 00:00:01 |
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
3 consistent gets
0 physical reads
0 redo size
532 bytes sent via SQL*Net to client
519 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed
SQL> select x from big_data where x = 12345;
Statistics
----------------------------------------------------------
1 recursive calls
0 db block gets
3 consistent gets
1 physical reads
0 redo size
534 bytes sent via SQL*Net to client
519 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed
SQL> select x from big_data where x = 1234567;
Statistics
----------------------------------------------------------
1 recursive calls
0 db block gets
3 consistent gets
5 physical reads
0 redo size
342 bytes sent via SQL*Net to client
508 bytes received via SQL*Net from client
1 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
0 rows processed
Note
B*Tree는 큰 테이블과 작은 테이블에서 모두 잘 동작하며 태이블의 크기가 커짐 에도 성능 저하가 거의 없는 범용목적의 인덱스기법 이다.
인덱스 키 압축
- B*Tree 인덱스를 압축할 수 있다는 것이다 ZIP 파일 압축과 같은 방식이 아니라 복합컬럼 (다수 컬럼) 인덱스 (결합 인덱스) 의 중복을 제거하는 것이다 (반복되는 값에 대한 공간 오버헤드를 줄이는 것이다).
- 압축 키 인덱스의 기본 개념은 모든 엔트리는 접두사 (prefix)와 접미사 (suffix) 두 부분으로나누어진다는 것이다. 접두사는 복합 컬럼의 앞부분으로 중복되는 값이 많이 존재하는 부분이고， 접미사는 인덱스 키 컬럼의 뒷부분으로 같은 접두사 안에서 고유한 값을 가진다.
Note
DBMS_STATS는 객체의 통계정보를 수집하는 데 사용되어야 하며, ANALYZE 영렁어는 인덱스 구조를 확인하거나 체인이 발생한 로우의 리스트를 확인하는 데 사용된다.
다음으로 인덱스 키를 압축하여 재생성해보기
create table t
as select * from all_objects
where rownum <= 50000;
create index t_idx on t(owner , object_type , object_name);
analyze index t_idx validate structure ;
create table idx_stats
as
select 'noncompressed' what , a.*
from index_stats a;
create table idx_stats
as
select 'noncompressed' what , a.*
from index_stats a;
drop index t_idx;
create index t_idx on
t(owner,object_type,object_name)
compress &1;
analyze index t_idx validate structure;
select 'compress &1' , height , lf_blks , br_blks , btree_space , opt_cmpr_count , opt_cmpr_pctsave from index_stats a;
--select what , height , lf_blks , br_blks , btree_space , opt_cmpr_count , opt_cmpr_pctsave
--from idx_stats;
WHAT HEIGHT LF_BLKS BR_BLKS BTREE_SPACE OPT_CMPR_COUNT OPT_CMPR_PCTSAVE
------------- ---------- ---------- ---------- ----------- -------------- ----------------
noncompressed 3 362 3 2920096 2 28
compress 1 3 324 3 2614800 2 19
compress 2 3 259 3 2095060 2 0
compress 3 3 404 3 3254480 2 35
결론
- 1 개 컬럼을 압축할 경우는 압축하지 않은 인덱스의 89% 정도 크기 (B1REE_SP ACE) 인 것을 볼 수 있다.
- 압축 2를 사용했을 경우는 더 많은 공간이 절약되었다. 비압축 인덱스 크기의 72% 정도 크기로 감소하였고 인덱스 높이가 3에서 2로 줄어들어 각각의
블록에 저장할 수 있었다. - 압축3 의 경우는 오히려 안좋아졌다. 이유는 접두사의 중복은 제거하여 반복되는 공간은 절약할 수 있었지만， 리프 블록에 압축 스키마 정보 4바이트 크기의 오버헤드를 추가했기 때문이다.
- 압축은 비용을 수반한다. I/0 시간이 줄어드는 반면 CPU시간이 증가하는 반대급부가 발생한다.
- 압축된 인덱스를사용하게 되면 이전보다 더 많은 인덱스 엔트리가 버퍼 캐시에 존재하게 되고 버퍼 캐시의 히트율(hit ratio) 이 증가함으로써 물리적 I/0는 감소하
게 된다. 그러나 인덱스를 다루기 위해서 CPU를 조금 더 사용한다.
리버스키 인덱스
- B*Tree 인덱스의 다른 특정은 키를 역으로 뒤집을 수 있다.(컬럼값의 역순)
- 리버스 키 인덱스는 특별한 상황과 특별한 목적을 위해 설계되었다. 오라클 RAC 환경에서 시퀀스 값 또는 타임스탬프 (timestamp) 값으로 생성되는 컬럼의 인덱스와 같이 오른쪽 (right-hand-side) 으로 증가히는 인덱스에 대한 리프 블록의 경합을 줄이기 위해 고안되었다.
- 일반적인 인덱스가 적용되는 모든 경우에 사용할 수 없다
- where x > 5 같은 조건 인덱스 사용안됨(인덱스의 데이터가 X 값으로 정렬되어 저장되어 있지 않고 REVERSE(X) 에 의해 저장되어 있기 때문)
- 결합 인덱스 (X. Y) 인 경우 ( where x = 5 ) 같은 조건은 리버스 키 인덱스를 사용할 수 있다
drop table t ;
create table t tablespace assm
as
select 0 id, a.\*
from all_objects a
where 1=0;
alter table t
add constraint t_pk
primary key(id)
using index ( create index t_pk on t (id) reverse tablespace assm);
create sequence s cache 1000;
create or replace procedure do_sql
as
begin
for x in ( select rownum r, all_objects.* from all_objects )
loop
insert into t (ID
,OWNER
,OBJECT_NAME
,SUBOBJECT_NAME
,OBJECT_ID
,DATA_OBJECT_ID
,OBJECT_TYPE
,CREATED
,LAST_DDL_TIME
,TIMESTAMP
,STATUS
,TEMPORARY
,GENERATED
,SECONDARY
,NAMESPACE
,EDITION_NAME)
values
( s.nextval
,x.OWNER
,x.OBJECT_NAME
,x.SUBOBJECT_NAME
,x.OBJECT_ID
,x.DATA_OBJECT_ID
,x.OBJECT_TYPE
,x.CREATED
,x.LAST_DDL_TIME
,x.TIMESTAMP
,x.STATUS
,x.TEMPORARY
,x.GENERATED
,x.SECONDARY
,x.NAMESPACE
,x.EDITION_NAME
);
if ( mod(x.r , 100) = 0 )
then
commit;
end if;
end loop;
commit;
end ;
/
pl-sql , pro*C을 동시 수행했을때 비교
 |
 |
 |
 |
내림차순 인덱스
- 내림치순 인덱스는 B*Tree 인덱스의 확장 기능으로서 오라클 8i 버전에서 소개되었다.
- 오름차순(작은값에서 큰 값으로) 대신에 내림차순(큰 값에서 작은 값으로)으로 정렬되어 저장하는 인덱스를 의미한다.
- 오라클 8i 버전 이상에서의 DESC 키워드는 인덱스의 생성 및 사용방식에 변화를 가져왔다
예제
-- 인덱스 역순으로 읽은예 - SORT 작업이 없음
drop table t ;
create table t
as
select *
from all_objects;
create index t_idx on t( owner ,object_type , object_name);
begin
dbms_stats.gather_table_stats
( user, 'T' , method_opt=> 'for all indexed columns' );
end;
select owner , object_type
from t
where owner between 'T' and 'Z'
and object_type is not null
order by owner DESC, object_type DESC;
Plan hash value: 2685572958
-------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 357 | 5712 | 5 (0)| 00:00:01 |
|* 1 | INDEX RANGE SCAN DESCENDING| T_IDX | 357 | 5712 | 5 (0)| 00:00:01 |
-------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("OWNER">='T' AND "OWNER"<='Z')
filter("OBJECT_TYPE" IS NOT NULL)
-- 인덱스 복합 수행 - SORT 작업이 생김
select owner , object_type
from t
where owner between 'T' and 'Z'
and object_type is not null
order by owner DESC, object_type ASC;
Plan hash value: 2813023843
---------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 357 | 5712 | 6 (17)| 00:00:01 |
| 1 | SORT ORDER BY | | 357 | 5712 | 6 (17)| 00:00:01 |
|* 2 | INDEX RANGE SCAN| T_IDX | 357 | 5712 | 5 (0)| 00:00:01 |
---------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - access("OWNER">='T' AND "OWNER"<='Z')
filter("OBJECT_TYPE" IS NOT NULL)
--owner 인덱스 내림차순 , object_type 오름차순 수행 - SORT 작업이 없음
drop index t_idx;
create index t_idx on
t(owner desc , object_type asc) ;
select owner , object_type
from t
where owner between 'T' and 'Z'
and object_type is not null
order by owner DESC, object_type ASC;
Plan hash value: 2946670127
--------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 357 | 5712 | 2 (0)| 00:00:01 |
|* 1 | INDEX RANGE SCAN| T_IDX | 357 | 5712 | 2 (0)| 00:00:01 |
--------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access(SYS_OP_DESCEND("OWNER")>=HEXTORAW('A5FF') AND
SYS_OP_DESCEND("OWNER")<=HEXTORAW('ABFF') )
filter(SYS_OP_UNDESCEND(SYS_OP_DESCEND("OWNER"))>='T' AND
SYS_OP_UNDESCEND(SYS_OP_DESCEND("OWNER"))<='Z' AND "OBJECT_TYPE" IS NOT
NULL)
언제 B*Tree 인덱스를 사용해야 하는가?
- 전체 테이블 로우 수에 비해 선택하려는 로우 수가 적은 경우는 B*Tree 인덱스만을 사용한다.
- 테이블의 많은 로우를 처리하지만， 인덱스만으로 처리할수 있다면 B*Tree 인덱스를 사용한다.
- 위의 상황에 인덱스를 사용하는 두 가지 방법
테이블의 로우에 접근하는 방법으로서
- 테이블의 로우를 액세스하기 위해 인덱스를 읽을 수 있을것이다. 여기서는 전체 테이블의 로우 수에 비해 매우 적은 로우를 접근하려고 할 때다.
select owner, status
from t
where owner = USER;
Plan hash value: 470836197
-------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 3709 | 48217 | 23 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID| T | 3709 | 48217 | 23 (0)| 00:00:01 |
|* 2 | INDEX RANGE SCAN | T_IDX | 247 | | 15 (0)| 00:00:01 |
-------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - access(SYS_OP_DESCEND("OWNER")=SYS_OP_DESCEND(USER@!))
filter(SYS_OP_UNDESCEND(SYS_OP_DESCEND("OWNER"))=USER@!)
- TABLE ACCESS BY INDEX ROWID를 수행해야만하는 경우에는 태이블 전체 블록 중 소량만을 읽도록 해야만 한다. 즉 전체 로우 중에 소량의 로우를읽어서 최대한 빨리 첫 번째 로우를 추출할 필요가 있는지 확인해 야 한다. 만약 테이블 로우의 대부분을 추출해야 하는 경우라면(추출 대상 로우가 20% 이상이라면)，B*Tree를 경유하는 것이 태이블 전체를 스캔하는 것보다 더 오래 걸릴 것이다.
쿼리에 응답하는 수단으로서
- 인덱스가 쿼리에 응답하기 위한 충분한 내용이 있는 경우라서 테이블에 접근할 필요가 없는 경우다. 이 경우는 인덱스가 테이블의 또 다른 축소판이 될것이다.
select count(*)
from t
where owner = USER;
Plan hash value: 293504097
---------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 6 | 15 (0)| 00:00:01 |
| 1 | SORT AGGREGATE | | 1 | 6 | | |
|* 2 | INDEX RANGE SCAN| T_IDX | 3709 | 22254 | 15 (0)| 00:00:01 |
---------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - access(SYS_OP_DESCEND("OWNER")=SYS_OP_DESCEND(USER@!))
filter(SYS_OP_UNDESCEND(SYS_OP_DESCEND("OWNER"))=USER@!)
- 인덱스만으로 결과를 처리하는 방식에 관한 이야기다. 하나의 인덱스 블록을 읽어서 많은 로우를 처리하고 다음 인덱스 블록을 읽어 나가는 방식으로 진행하고 테이블에는 접근하지 않았다.
물리구조
- 데이터를 물리적 디스크에 구조화하는 방식은 데이터 처리 에 영향을 주고 인덱스 액세스 비용에 영향을 주게 된다.
- 데이터를 테이블에 삽입할 때 시퀀스에 의해 생성되는 기본 키를 가진 테이블은 순차적으로 증가하는 시퀀스 숫자 값을 순서로 다음 로우와 서로 인접해 있게 된다 ( 일반적으로 기본키 값이 서로 가까운 로우들은 물리적으로도 인접한 위치에 있게 된다)
select * from T where primary_key between :x and :y
- 추출하고자하는 로우가 일반적으로 동일블록에 저장될 수 있다 이 경우에는 많은 양의 로우들에 접근하더라도 인덱스 범위 스캔이 효율적이다. 왜냐하면 데이터 들이 인접해 있으므로 반복적으로 읽게될 블록들이 대부분 캐시되어 있을 것 이기 때문이다.
로우가 인접해 있지 않은 경우에 동일 인덱스를 사용하게 되면，속도에 심각한 문제가 발생된다.
drop table colocated ;
create table colocated ( x int, y varchar2(80) );
begin
for i in 1 .. 100000
loop
insert into colocated(x ,y)
values (i, rpad(dbms_random.random,75,'*' ));
end loop;
end;
alter table colocated
add constraint colocated_Pk
primary key(x);
begin
dbms_stats.gather_table_stats( user, 'COLOCATED' ) ;
end;
- 블록의 크기가 8킬로바이트고 한 블록당 100개의 의 로우가 저장되는 앞의 예와 같은 테이블인 경우， 이테이블에는 X=l,2,3 이 같은 블록에 존재할 가능성이 매우 크다. 이제 의도적으로 이 테이블의 로우를 분산시켜 보자 COLOCATED 테이블에 랜덤 숫자로 구성된 컬럼 Y를 이용하여 데이터를 분산시켜서 더 이상 기본키값의 순서로 정렬 되 지 않도록 할 것이다.
create table disorganized
as
select x,y
from colocated
order by y;
alter table disorganized
add constraint disorganized_Pk
primary key (x);
begin
dbms_stats.gather_table_stats( user, 'disorganized' ) ;
end;
- TKPROF 결과
select *
from
colocated where x between 20000 and 40000
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 5 0.00 0.00 0 0 0 0
Execute 5 0.00 0.00 0 0 0 0
Fetch 55 0.04 0.03 0 465 0 25250
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 65 0.04 0.03 0 465 0 25250
Misses in library cache during parse: 1
Optimizer mode: ALL_ROWS
Parsing user id: 84
Rows Row Source Operation
------- ---------------------------------------------------
5050 TABLE ACCESS BY INDEX ROWID COLOCATED (cr=93 pr=0 pw=0 time=2524 us cost=283 size=1620162 card=20002)
5050 INDEX RANGE SCAN COLOCATED_PK (cr=22 pr=0 pw=0 time=757 us cost=43 size=0 card=20002)(object id 74640)
********************************************************************************
select /*+ index( disorganized disorganized_pk ) */* from disorganized
where x between 20000 and 40000
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 5 0.00 0.00 0 0 0 0
Execute 5 0.00 0.00 0 0 0 0
Fetch 55 0.06 0.05 0 25355 0 25250
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 65 0.06 0.06 0 25355 0 25250
Misses in library cache during parse: 1
Optimizer mode: ALL_ROWS
Parsing user id: 84
Rows Row Source Operation
------- ---------------------------------------------------
5050 TABLE ACCESS BY INDEX ROWID DISORGANIZED (cr=5071 pr=0 pw=0 time=8078 us cost=20041 size=1620162 card=20002)
5050 INDEX RANGE SCAN DISORGANIZED_PK (cr=22 pr=0 pw=0 time=631 us cost=43 size=0 card=20002)(object id 74642)
- 물리 데이터의 구조의 차이가 다른 결과를 가져왔다.
 |
테이블 전체 블록 수
select
a.index_name,
b.num_rows,
b.blocks,
a.clustering_factor
from user_indexes a, user_tables b
where index_name in ( 'COLOCATED_PK', 'DISORGANIZED_PK')
and a.table_name = b.table_name
INDEX_NAME NUM_ROWS BLOCKS CLUSTERING_FACTOR
------------------------------ ---------- ---------- -----------------
COLOCATED_PK 100000 1252 1190
DISORGANIZED_PK 100000 1219 99921
- DISORGANIZED 테이 블에 대한 수행 결과는 앞에서 살펴본 것처럼 간단하게 계산할 수 있다.20,000 + 논리 1/ 0를 수행할 것을 예상했다
- 반면에 물리적으로 COLOCATED된 데이터 는 더 적은 논리 I/0를 수행하였다.
- 실제 운영 시스템에서 데이터를 덤프해서 개발 서버에 로드하는 경우에 "이 서버에서 다르게 동작할까， 동일하게 동작할까?"라는 질문에 대한 좋은 답변 중 하나가 될 것이다. 실제로 동일하게 동작하지 않는다.